[파이썬] 백준 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을 출력한다.

구상

각 자릿수를 구해 리스트에 저장하고, 리스트 요소의 합이 입력받은 수 n과 같으면 flag를 1로 설정해 생성자가 존재함을 나타낸다. flag에 따라 출력값을 설정한다.

코드

n = int(input())
flag = 0	//초기 플래그는 0으로 설정

for i in range(n+1):	//n까지 반복. i는 생성자 역할
    k = i		//임시 변수 생성
    num = list()	//리스트 생성
    num.append(k)	//리스트에 생성자 수 자기자신을 추가
    while(k != 0):	//모든 자릿수를 구할 때까지 반복
        num.append(k % 10)	//일의 자리 추가
        k //= 10		//일의 자리 제외
    if sum(num) == n:	//생성자가 존재하면
        flag = 1		//플래그를 1로 설정하고
        break			//반복 종료
    
if flag == 0:	//생성자가 없는 경우
    print(0)
else:			//생성자가 있는 경우
    print(i)