[백준] 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 <stdio.h>

int    get_length(int n)
{
    int    i;

    i = 0;
    while (n)
    {
        n /= 10;
        i++;
    }
    return (i);
}

int    get_generator(int n, int length)
{
    int    start;
    int    backup;
    int    gen;
    int    i;

    start = n - (9 * length);
    while (start <= n)
    {
        i = -1;
        gen = start;
        backup = start;
        while (++i < length)
        {
            gen += backup % 10;
            backup /= 10;
        }
        if (gen == n)
            return (start);
        start++;
    }
    return (0);
}

int    main(void)
{
    int    n;
    int    length;
    int    start;
    int    i;

    scanf("%d", &n);
    length = get_length(n);
    if (length == 1)
    {
        if (n % 2 == 0)
            printf("%d", n / 2);
        else
            printf("0");
    }
    else
        printf("%d", get_generator(n, length));
}

반성회

노력했다

사실 문제이해도 잘 안돼서 이것저것 찾아보다 앎 ㅋㅋ 어떻게 생각을 그렇게 하지

역시 알고리즘 잘하는애들은 똑똑이구나