문제
접근
어떤 수의 생성자 중 최소값을 찾아야 한다.
최소값을 찾기 위해 1부터 모두 확인해봐야 할까?
가능은 하겠지만 비효율적일 것 같다.
예를 들어, 1000000의 생성자를 찾는데 굳이 1부터 확인해야 할까?
그럼 생성자를 찾을 때 어디서부터 찾기 시작해야 할까?
분해합을 만들기 위해선 결국 생성자 자신과 자신의 자릿수의 합이다.
그럼 자릿수의 합 만큼 빼주면 생성자가 나온다는 얘기다.
각 자리의 최대값은 9이므로, 전체 자리 * 9를 빼주면 가장 최소의 경우가 나올 것이다.
예를 들어, 198의 생성자를 찾을 때, 1부터 찾는게 아니라 198은 3자리이므로, 3*9=27.
198 - 27 = 171부터 찾기 시작해도 된다.
그 이하의 수는 절대 198을 분해합으로 만들지 못한다.
저 최소값을 x라고 하면, x부터 주어지는 분해합 n까지만 확인하면 된다.
생성자는 절대 분해합보다 클 수 없으므로.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def makeSum(x):
ans = x
while x > 0:
ans += (x % 10)
x //= 10
return ans
n = int(input())
t = len(str(n))
x = n - t*9
x = 1 if x < 1 else x
ans = 0
for i in range(x, n):
if makeSum(i) == n:
ans = i
break
print(ans)