백준(BOJ) 2231번 분해합

문제 : https://www.acmicpc.net/problem/2231

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

나의 풀이:

N의 가장 작은 생성자를 구해야 하고 N이 100만 까지이니 1부터 시작하는 완전 탐색으로 충분히 시간 내에 가능하다. 

i를 1부터 시작해서 i의 수 + i의 각자리의 수 가 N과 같다면 탐색을 종료한다. 100만까지 다 돌았음에도 ans의 값이 -1에서 갱신되지

않았다면 생성자가 없는 경우이므로 0을 출력해준다.

코드 ( C++ )

#include <iostream>

using namespace std;

int main()

{

int N;

cin >> N;

int ans = -1;

for (int i = 1; i <= 1000000; ++i)

{

// i 는 바뀌지 않도록 here을 하나 만든다.

int here = i;

int sum = 0;

while (here != 0) {

sum += (here % 10);

here /= 10;

}

if (N == (i + sum)) {

ans = i;

break;

}

}

// 초기화한 ans의 값이 100만 이후에도 -1이라면 답이 없으니 0을 출력해준다.

if (ans == -1)

cout << 0 << "\n";

else

cout << ans << "\n";

return 0;

}