[BOJ] 2231

분해합

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

분류

• Bronze 2

• 브루트포스 알고리즘

해법

백만이 입력으로 들어왔을 때 시간적 손해가 크므로
1부터 1,000,000까지를 모두 백만의 생성자인지 확인할 수는 없습니다.
따라서, 확인할 범위를 정하는 것이 가장 중요합니다.
4자리 수인 n이 있다면 n의 생성자는 n - 9 * 4 보다 작아질 수 없음을 활용하시면 됩니다.

정답 코드

#include <iostream>
using namespace std;

int DigitCnt(int n) // cal digits
{
    int cnt = 0;
    while ( n > 0 )
    {
        n /= 10;
        cnt++;
    }
    return cnt;
}

int DigitSum(int n) // add all digits
{
    int sum = 0;
    int m = 10;
    while ( n > 0 )
    {
        int add = n % m;
        sum += add;
        n /= m;
    }
    return sum;
}

int Constructor(int n)
{
    int start = n - DigitCnt(n) * 9; // constructor of n can't be smaller than n - DigitCnt(n) * 9
    int dest = n - 1; // also can't be bigger than n - 1
    for (int i = start; i <= dest; i++)
    {
        int result = i + DigitSum(i);
        if (result == n)
            return i;
    }
    return 0;
}

int main(void)
{
    int n;
    cin >> n;
    cout << Constructor(n);
    return 0;
}