[백준 2231] 분해합

최악의 경우로 1부터 1,000,000까지 돌면서 분해합을 구해야 한다고 가정해보자.

어떤 수 x의 분해합을 구하기 위하기 위해선 x의 자리 수만큼의 시간이 필요하다. 

따라서 \((1 \times 10) + (2 \times 100) + (3 \times 1000) + ... + (5 \times 100000) + (6 \times 1) = 1,543,210\)번의 연산이 필요하고, 이는 문제에서 주어진 2초 안의 충분히 해결할 수 있는 연산량이다. 때문에 브루트 포스로 해결하자 !

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 10e+8;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, ans = 0;
	cin >> n;
	// 생성자는 n보다 작을 수 밖에 없다.
	for (int i = 1; i <= n; i++) {
		int cur = i, sum = i;
		// 분해합 구하기
		while (cur) {
			sum += cur % 10;
			cur /= 10;
		}
		// 가장 작은 생성자를 구해야하기 때문에 찾자마자 for문 종료
		if (sum == n) {
			ans = i;
			break;
		}
	}

	cout << ans;

	return 0;
}