[C++] 백준 2231번 분해합

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

풀이

자연수 M의 분해합은 M + (M의 각 자리 수의 합) 이므로

만약 M이 한 자리 수라면, M의 분해합은 (M + M = 2M) 이고,
M이 xy라는 두 자리 수라면, M의 분해합은 (M + x + y) 이고,
M이 xyz라는 세 자리 수라면, M의 분해합은 (M + x + y + z) 이다.

x, y, z는 최대 9이므로 M의 분해합은 M의 차는 크지 않을 것이다.

따라서 어떤 자연수 N의 생성자를 구할 때,
N보다 작은, 어떠한 수 K부터 N까지 브루트포스 방식으로 탐색하면서
해당 수가 N의 생성자인지 아닌지 판단하였다.

K는 보수적으로 설정해야 하므로 N의 각 자리수가 9일 때를 기준으로 하였다.
즉, N이 두 자리 수일 때, K를 (N - 18) 로,
N이 세 자리 수 일 때, K를 (N - 27) 로 설정하였다.

코드

#include <iostream>

using namespace std;

int getSum(int num) {  // num의 분해합을 구하는 함수
    int sum = num;
    while(num > 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

int main()
{
    string s;
    cin >> s;
    
    int num = stoi(s);  // 입력받은 수 N
    int start = num - s.size() * 9;  // K 설정
    								 // s.size(): N이 몇자리 수인지
    
    int ans = 0;
    for(int i=start; i<=num; i++) {
        if(getSum(i) == num) {
            ans = i;
            break;
        }
    }
    
    cout << ans;
    
    return 0;
}