[알고리즘] 백준 2231번 "분해합" (C/C++) - Don 임베디드

문제요약:

자연수 N에 대하여, 그 자연수 N의 분해합은

"N + (N을 이루는 각 자리수의 합)" 을 의미한다.

어떤 자연수 M의 분해합이 N 인 경우,

"M은 N의 생성자" 라고 한다.

예를 들어,

245의 분해합은 256(=245 + 2 + 4 + 5) 이다.

따라서 245는 256의 생성자가 된다.

어떤 자연수의 경우에는 생성자가 없을 수도 있다.

반대로, 생성자가 여러 개 일수도 있다.

 

자연수 N이 주어졌을 때,

N의 가장 작은 생성자를 구하는 프로그램을 만들어보자.

 

제약:

시간제한 2초, 메모리 제한 192MB

N은 자연수, 1 <= N <= 1000000

 

출력:

N의 가장 작은 생성자를 출력한다.

생성자가 없는 경우 0을 출력.

 

예제 1 입력.	예제 1 출력.
256	245
예제 2 입력.	예제 2 출력.
216	198
예제 3 입력.	예제 3 출력.
198	0

 

 

정답코드:

#include <iostream>
 
using namespace std;
 
int GetDecomposeValue(int n)
{
    int nTmp = n;
    int nDecompVal = n;
 
    while (nTmp > 0)
    {
        nDecompVal += (nTmp % 10);
        nTmp /= 10;
    }
 
    return nDecompVal;
}
 
int main()
{
    int nTmp, nDigits;
    int nCandidateMinimum;
    int N;
    int nResult = 0;        // to print 0 if there's no answer.
 
    // Input N value
    cin >> N;
 
    nTmp = N;
    nDigits = 0;
 
    // Get Digit Num to set candidate search boundaries.
    while (nTmp > 0)
    {
        nTmp /= 10;
        nDigits++;
    }
 
    // if candidate is smaller than this value, stop searching.
    nCandidateMinimum = N - (nDigits * 9);
 
    if (nCandidateMinimum < 0)
    {
        nCandidateMinimum = 0;
    }
 
    // start from minimum candidate
    for (int j = nCandidateMinimum; j < N; j++)
    {
        if (GetDecomposeValue(j) == N)
        {
            nResult = j;
            break;
        }
    }
 
    // print result.
    cout << nResult << '\n';
    
    return 0;
}
 

 

원본 링크: https://www.acmicpc.net/problem/2231