문제
어떤 자연수 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 = int(input())
min = N - 9*len(str(N))
min = 1 if min<1 else min
for i in range(min, N+1):
check = i + sum(map(int, str(i)))
if N == check:
print(i)
break
if i == N:
print('0')
코드 설명
N에 입력값을 받아 저장한다.
for문을 1부터 N까지 돌릴 수도 있지만,
각 자리 수의 합이 제일 큰 생성자는 모든 자리수가 9인 수 일 것이다.
(가장 큰 생성자는 모든 자리수가 9인 수 이다.)
따라서 입력값 N에서 N의 자리수에 9를 곱한 수를 빼서 min에 저장한다.
자리수를 구할 때 len() 함수를 쓰기 위하여 N을 str로 바꾸고 대입해 주었다.
만약 N이 자리수*9를 한 수보다 작다면 음수가 될 것이다.
이를 판단하기 위하여 if문을 사용하였다.
만약 min이 1보다 작다면 min=1, 그렇지 않다면 넘어간다.
(이 과정을 거치지 않으면 런타임 에러가 뜬다!)
N = int(input())
min = N - 9*len(str(N))
min = 1 if min<1 else min
min부터 N까지 for문을 돌린다.
sum(map(int, str(i)))를 이용하면 각 자리수의 합을 쉽게 구할 수 있다.
check에 i와 i의 각 자리 수의 합까지 더하여 대입한다.
만약 N과 check이 같다면 i를 출력하고 for문을 종료한다.
그렇지 않고, N까지 진행된다면 이는 생성자가 없는 것이므로 0을 출력한다.
for i in range(min, N+1):
check = i + sum(map(int, str(i)))
if N == check:
print(i)
break
if i == N:
print('0')
for문을 1부터 돌려도 에러는 뜨지 않지만 min을 사용했을 때 보다 시간이 오래걸리는 것을 확인 할 수 있다.
min을 정의하지 않은 코드는 1392ms, 정의한 코드는 68ms 약 20배가 차이 난다.
