2231번 분해합

문제 링크

분해합

문제 풀이

자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라고 한다. 입력 N에 대해, N의 가장 작은 생성자를 구하는 문제이다.
N은 1이상 1,000,000 이하의 자연수이므로, 완전 탐색으로 구할 수 있다. 이때, 각 자리수 합의 최대는 6 * 9 = 54이므로 N - 54 에서부터 N 사이의 자연수만 고려하여 답을 계산한다.

구현

#include <iostream>
#include <string>
using namespace std;

int N;
int solve() {
    int i = (N - 56 >= 0) ? N - 56 : 0;

    for (; i <= N; ++i) {
        string num = to_string(i);
        int sum = 0;
        for (int j = 0; j < num.size(); ++j) {
            sum += num[j] - '0';
        }
        if (sum + i == N) return i;
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    cout << solve();
    return 0;
}