[BOJ:2231]분해합

it 취업을 위한 알고리즘 문제 풀이

문제

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

코드

import sys

n = int(sys.stdin.readline().rstrip())

for i in range(n):
    res = 0
    temp = i
    while temp:
        num = temp%10
        temp //= 10
        res += num

    if res+i == n:
        print(i)
        break
else:
    print(0)

문제해결방법

• 문제를 정확히 읽으면 쉽게 해결 할 수 있는 문제이다. 분해합, 생성자의 정의를 이해하고 분해합을 만드는 생성자는 분해합보다 작다라는 추론을 하면 브루트포스로 쉽게 구현할 수 있다.
• 생성자를 구하기 위해서는 주어진 N보다는 무조건 작은 숫자여야 한다. 이유는 N보다 큰 숫자로 N과 N의 각 자리수를 합해서 N을 만드는 생성자는 없기 때문이다.
• 1부터 차례대로 분해합을 구하면서 N이 되는 값을 찾으면 된다. N이 되면 구한 분해합은 N의 생성자이기 때문이다. 그리고 1부터 차례대로 구했기 때문에 처음 구해진 생성자가 가장 작은 생성자가 된다.