[🥉2 / 백준 2231 / 파이썬] 분해합

 

2231번: 분해합

 

문제

어떤 자연수 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을 출력한다.

 

예제 입력 216

예제 출력 198

 

풀이

 

 

반복문을 이용하면 매우 쉽게 풀릴 문제같으나,

입력 제한이 1 이상 1,000,000 이하로 범위가 매우 크다.

 

따라서 시간 초과를 피하기 위해 패턴을 찾을 필요가 있다.

 

우선, 1,000 이 입력으로 들어왔다고 생각해보자.

 

1,000 의 생성자를 x 라고 했을 때, x는 1,000 미만이므로 세 자리 수일 것이다.

각각의 자리수에서 들어올 수 있는 수는 0~9, 세 자리 수이므로 합은 27이 최대이다.

 

따라서 1,000 - 27 ~ 999 의 범위만 구하면 되는 것이다.

이를 일반화 하면 N - (N-1 자리수의 수 * 9) ~ N - 1이 된다.

 

n = int(input())

a = list(map(int,(str(n-1))))	# n-1의 자리수를 구함
for i in range(len(a)):
    a[i] = 9
least = n-sum(a)
# 모두 9로 바꾼 뒤 n에서 빼서 최솟값을 구함

for i in range (max(least,0), n):
# 18 미만의 수는 최솟값이 음수가 된다. 따라서 0부터 구하도록 해준다.
    if i + sum(list(map(int,(str(i))))) == n:
        print(i)
        break
else:
    print(0)