[브론즈2] 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을 출력한다.

예제 입력 1 복사

216

예제 출력 1 복사

198

 

문제풀이

N의 분해합 : N과 N을 이루는 각 자리수의 합
생성자 : 자연수 M의 분해합이 N인 경우, M을 N의 생성자
245의 분해합은 256(=245+2+4+5)
245는 256의 생성자
생성자가 없을수도 있음
생성자가 여러개 있을수도 있음
생성자 중에서 제일 작은 값을 구하여라

 

문제해결

1부터 n까지 생성자가 될수 있는 숫자 모두 찾는 형식

i에서 생성자 후보 숫자를 각각 한자리 씩 쪼개서 더함 = j

생성자 = i + 각 자리 더해서 만든 수(num)

n과 같은 수이면 생성자이면서 최소값으로 break

0부터 n까지 전부 순회했는데 같은 값이 없으면 생성자가 없는 숫자임

n = int(input())

for i in range(1, n+1) :    #1부터 n까지 생성자 될수 있는 목록 찾기
    num = 0                 #생성자는 각 수의 자리 수를 더해야하므로 매번 더한 자리수 저장 필요
    for j in str(i) :       #한자리씩 쪼개서 더해준다
        num += int(j)
    new_num = i + num       #생성자 = i + 더한 수
    if new_num == n : 
        print(i)
        break
    if i == n :
        print(0)