BOJ2231

BaekJoon 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을 출력한다.

나의 첫번째 답

#include <iostream>

// 분해합 찾는 함수
int decomposeSum(int n)
{
    int origin = n;
    int sum = 0;
    while(origin > 0)
    {
        int temp = origin % 10;
        sum += temp;
        origin /= 10;
    }
    return n + sum;
    
}

// 생성자 찾는 함수
int findInit(int n)
{
    for (int i = 1; i < n; i++)
    {
        if(decomposeSum(i) == n) return i;
    }

    return 0;
}

int main() {

    int N;
    std::cin >> N;

    std::cout << findInit(N) << std::endl;

    return 0;
}

이 문제는 브루트포스 단계로 구분되어있어서, 일말의 의심도 없이 정말 브루트포스하게 0부터 쭈욱 검사하는 방법으로 풀었다.

그러나 한번 더 생각해보면, 찾는 범위를 한정지을 수 있다. 자연수 N의 생성자를 찾을 때, 자연수 N의 각 자리에 올 수 있는 숫자 중 최대는 9 이므로, [자연수 N] - 9 * (자연수 N의 길이) ~ [자연수 N] - 1 로 찾는 범위를 한정짓는 것이 가능하다.

물론 이는

그리서 이를 코드로 풀면

두번째 답

// 생성자 찾는 함수
int findInit(int n)
{
    // 탐색 범위를 줄임
    int start = std::max(1, n - 9 * static_cast<int>(std::to_string(n).length()));

    for (int i = 1; i < n; i++)
    {
        if(decomposeSum(i) == n) return i;
    }

    return 0;
}

위와 같이, 시간을 좀 더 단축시킬 수 있다.