문제
어떤 자연수 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
풀이
생성자가 주어지고 분해합을 구하는 것이 아니라, 그 반대로 분해합이 주어지고 생성자를 구하는 것이다.
분해합이 만약 최대 수인 1,000,000이 된다면 생성자는 1,000,000 이하가 될 것이다.
즉, 생성자는 최대 6자리 수
만약 생성자가 6자리 수 중에 제일 큰 수인 999,999라고 예를 들면,
분해합은 999,999 + (9*6) 이다.
따라서 분해합과 생성자가 제일 크게 차이나는 경우가 9*6 = 54가 차이나는 경우다.
분해합은 생성자보다 최대 54가 크다
이것을 이용하여 계산해보면, 분해합 N이 주어지면, N-54 ~ N-1의 범위에서 살펴보면 된다.
코드
num = int(input())
result = 0
for i in range(num - 54, num - 1):
a = 0
temp = i
answer = i
while temp >= 10:
a = temp % 10
temp = int(temp / 10)
answer += a
answer += temp
if answer == num:
result = i
break
print(result)for문을 이용하여 num - 54 ~ num - 1 까지 탐색한다.
temp에 임시로 i를 대입하였고, answer에 i를 대입하였다. 분해합을 구할 때, 생성자 자기 자신을 먼저 더한 뒤에 부가적인 연산을 진행하기 때문이다.
temp가 10보다 같거나 클 때 까지 while문을 돌리고, temp를 계속 10으로 나누고 그 나머지를 a변수에 저장하고 answer에 더해준다. temp는 10으로 나눈 몫을 계속 대입하여 while문을 유지할 수 있도록 한다.
temp가 10보다 작을 때는 while문을 돌지 않으므로 마지막으로 answer += temp를 해준다. answer와 num이 같으면 result는 i로 결정된다.
