📒 문제
어떤 자연수 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에 대한 가장 작은 생성자를 구해내는 것이므로 for문을 사용해서 N번의 횟수를 순서대로 반복해서 맞는 값을 발견하면 break하는 방법을 사용해보았다.
n = int(input())
chk = 0
for k in range(n):
num_list = list(map(int, list(str(k))))
result = 0
for i, v in enumerate(num_list):
result += v * (10**(len(num_list)-1-i))
if result + sum(num_list) == n:
chk = 1
break
if chk == 1:
print(result)
else:
print(0)이 방법을 사용하여 풀이에 성공했다. 하지만 N의 범위가 백만까지이기 때문에 적은 횟수의 2중반복이지만 for문을 2번 사용하면 시간에서의 효율성이 떨어지게 된다.
실제로 메모리는 29200kb이지만, 시간은 4572ms라는 결과를 얻었다.
하지만 pypy3를 통해 채점해본 결과, 메모리는 125628kb, 시간은 640ms라는 결과를 얻을 수 있었다. 두 채점 방식 사이에 큰 차이가 있음을 볼 수 있었다.
.
.
.
다음의 풀이를 실행해보았다.
n = int(input())
result = 0
for i in range(1, n+1):
num_list = list(map(int, str(i)))
result = i + sum(num_list)
if result == n:
print(i)
break
if i == n:
print(0)과정을 줄이니 메모리는 유지하며, 시간은 1636ms로 큰 차이를 보이며 줄일 수 있었다.
항상 불필요한 과정은 없었는지 생각하며 코드를 작성해야한다는 것을 깨달았다.
