[백준] 브루트포스 - 2231. 분해합

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

 

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

 

예제 입력1

216

 

예제 출력1

198

 

생각

처음에 문제를 봤을때 나눗셈으로 풀릴 거 같았다. 그래서 몫과 나머지 구하기 문제로 생각을 하고 divide() 함수를 구현했다. 그러다가 타임아웃이 날꺼같은 불안감에 for문의 인덱스를 n부터 시작하려고 했는데, 문제를 다시 봤더니 가장 작은 생성자를 구하는 것이기 때문에 다시 0부터 시작하는 것으로 바꾸고 제출했다. 

그런데, 틀렸습니다... 아니 왜?!! 여기서 또한번 문제를 제대로 읽지 않은 실수를 발견했다. 출력에서 생성자가 없는 경우에는 0을 출력해야된다는 조건이었다. 그래서 flag를 선언해서 찾지 못한 경우 0을 출력하게끔 고쳤다.

flag를 false로 선언하고 찾았을때 true로 하는 것보다 flag를 true로 하는 것이 시간을 더 단축시킬수 있다.(4ms)

 

작성한 코드

#include <iostream>
using namespace std;

int s,r;
int n;
bool flag = true;
int divide(int m, int sum){
    s = m/10;
    r = m%10;

    if(s!=0){
        sum += r;
        return divide(s, sum);
    }else{
        sum += r;
    }
    return sum;
}
int main(int argc, const char * argv[]) {
    // insert code here...
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    int result;

    for(int i=0; i<n; i++){
        result = divide(i, i);
    
        if(result == n){
            cout << i <<"\n";
            flag = false;
            break;
        }
    }
    
    if(flag){
        cout << 0 <<"\n";
    }

    return 0;
}