[백준/python] 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을 출력한다.

 

정답

import sys
input = sys.stdin.readline

N = int(input())

answer = N // 2

while N > answer:
    sum = answer
    for i in str(answer):
        sum += int(i)
    if sum == N:
        break
    answer += 1

if answer >= N:
    answer = 0

print(answer)

---

브루트포스 알고리즘으로 요령없이 모든 경우의 수를 따져봐야한다.

경우의 수를 조금이라도 줄이기 위해 1부터 시작이 아닌 입력받은 N의 절반부터 시작한다.

answer에 생성자 후보를 저장하고 answer이 N보다 작을 동안,

sum에 분해합을 구하여 저장하고 N과 비교한다.

 

분해합을 구할 때 각 자리수를 더하기 위해 answer을 str로 변환하여 for문을 이용해 한글자씩 불러와

다시 int로 변환하여 sum에 더한다.

 

while문을 나왔을 때 answer이 N보다 크거나 같다면 생성자가 없다는 뜻이므로 answer에 0을 저장한다.