[백준 2231] 분해합

처음 접근할 때에는 모든 분해합을 구하면서 가장 작은 생성자를 구하려고 했다. 이럴 경우 숫자가 커지면 커질수록 생성자를 계산하는 과정이 늘어나게 된다. 해법은 입력으로 들어온 숫자에서 자리수 * 9를 빼주면 범위를 상당히 좁힐 수 있다. 아래는 해당 구현법을 적용한 C++ 소스이다.

 

#include <iostream>

using namespace std;

int cntPos(int number) {
    int cnt = 0;
    while (number) {
        number /= 10;
        cnt++;
    }
    return cnt;
}

int sumPosNumbers(int number) {
    int sum = 0;
    while (number) {
        sum += number % 10;
        number /= 10;
    }
    return sum;
}

int main() {

    int number;
    cin >> number;
    
    int originPart = number - (cntPos(number) * 9);
    for (int index = originPart; index <= number; index++) {
        int testNum = index + sumPosNumbers(index);
        if (testNum == number) {
            cout << index << endl;
            return 0;
        }
    }

    cout << 0 << endl;

    return 0;
}