문제
어떤 자연수 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을 출력한다.
풀이
num = int(input())
res = flag = 0
for i in range(1, num+1):
res = sum(map(int, str(i)))
if num == (i + res):
print(i)
flag = 1
break
if flag == 0:
print(0)1에서부터 n까지 해당 값과 그 값을 이루는 자리수의 합이 입력값과 동일한지 확인하는 문제였다.
sum(map(int, str(i))) : 해당 숫자를 str 형으로 변환하면 배열처럼 사용할 수 있다. 각 자리수를 나누어 int 형으로 변환해 준 뒤, 합을 구한다.
실행시간이 너무 오래걸려 개선할 방법을 찾아보았다. ( 다른분의 글 참고 )
입력받은 num 에서 생성자를 구하기 위해서는 생성자의 각 자리의 수를 더한 값을 빼야한다.
예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다.
이때 256 - ( 2+ 4+ 5 ) = 245가 되고, 생성자를 구하기 위한 최소값은
256 - ( 9 + 9 + 9 ) 일 것이다. 따라서 입력값의 길이만큼 9를 곱하여 빼주면 생성자의 최소값을 구할 수 있을 것이다.
참고코드
num = int(input())
start = num - (len(str(num)) * 9)
start = 1 if start < 1 else start
ans = 0
for i in range(start, num+1):
res = sum(map(int, str(i)))
if num == (i + res):
ans = i
break
print(ans)처음엔 start 가 음수가 나올 것을 생각해 abs(num - (len(str(num)) * 9)) 로 사용했는데 계속 실패가 떴다. 아마 최소값이 달라지기 때문 아닐까,,? 그래서 start 가 음수일 경우에는 1로 대입하여 처음부터 비교하도록 수정했다.
