백준 2231 분해합 - C++

접근

문제에서 보면 245는 256(245+2+4+5)의 생성자다

그런데 어떠한 N이 나왔을 때 N의 생성자를 알아내기 위한 규칙성을 찾기가 어렵다..어쩌면 없을지도 

N이 2020일때 2020의 생성자는 2009인데 규칙성을 찾을 수가 없다.

 

따라서 브루트포스로 해결해야 하는 문제인데

숫자 1부터 높여가며 N의 생성자가 될 수 있는지 확인하는 과정을 거치면 O(N)이고 N은 백만보다 작으니 충분히 해볼만 하다.

 

#include <iostream>
#include <string>
using namespace std;
int makeSum(int num){
    int result = num;
    string str = to_string(num);
    for(int i=0; i<str.size(); i++){
        result += str[i]-'0';
    }
    return result;
}
int main()
{
    int limit = 1000001;
    int N;
    cin >> N;
    for(int i=1; i<=limit; i++){
        if(makeSum(i) == N) {
            cout << i << '\n';
            break;
        }
        if(i > N){
            cout << 0 << '\n';
            break;
        }
    } 
    return 0;
}

 

makeSum 함수에서 각 자릿수에서 - '0'을 해주는데 그 이유는

현재 num이 216이라고 가정하면 str에는 "216"이 들어가 있다 다시 말해 문자열이다.

따라서 문자를 그대로 더하기 연산을 해줄 수 없으니 변환해 줘야 한다.

첫번째 자릿수가 '2'이고 ascii 코드로 변환하면 50이다. '0'은 48이다 50-48 = 2이기 때문에 해당 자릿수에 있는 문자형 숫자를 int형 숫자로 얻을 수 있다.