2231번. 분해합 - C++

문제 링크

분해합

코드

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

int main() {
    string s;
    cin >> s;
    
    int s2 = stoi(s), s3 = stoi(s), m = 0, result = 0;
    
    // s의 자릿 수 세기
    while (true) {
        m++;
        s2 /= 10;
        if (s2 == 0) break;
    }
    
    // 범위 내 숫자가 생성자인 지 확인
    for (int i = s3 - 9 * m; i <= s3 ; i++) {
        int sum = i;
        string ss = to_string(i);
        
        for (int j = 0; j < ss.length(); j++) {
            // ss[j]가 char형이므로 '0'의 아스키 코드 값을 빼주고 sum에 더함
            sum += (int) ss[j] - '0';
        }
        
        if (sum == s3) {
            result = i;
            break;
        }
    }
    
    cout << result;
    return 0;
}

설명

1. s의 자릿수를 구한다.
2. s - s의 자릿수 * 9부터 반복문을 시작한다. (왜 그런지는 밑에서 설명)
3. 반복문 내에선 i를 생성자로 분해합을 구하고, 구한 분해합이 s와 같은지 확인한다. 같다면 i가 s의 생성자인 것이다. (작은 값부터 시작하기 때문에 가장 최소가 되는 생성자를 구하면 바로 break 하면 된다.)
4. result를 출력한다.

생성자의 범위?

생성자인지 아닌지 판단하기 위해선 생성자의 범위부터 정의해야 한다.
ABC인 세 자리 수의 정수를 생성자라고 치면, 분해합은 A + B + C + ABC가 된다.
이때, A + B + C의 최대 값은 27이 된다.

같은 방식으로 ABCD인 네 자리 수의 정수를 생각하면, A + B + C + D의 최대 값은 36이 된다.

즉, 분해합의 생성자 범위는 그 숫자에 숫자의 자릿수와 9를 곱한 값을 뺀 값이 된다.

배운 점

분해합이란 걸 처음 들어봐서 신기했다. 그리고 아무래도 브루트 포스 알고리즘은 나랑 안 맞는거 같다…