백준 BaekJoon Online Judge // 2231

백준 알고리즘 BaekJoon Online Judge 2231번 "분해합" 문제입니다.

N = input()
sumN = 0
lst = []
for i in range(max(int(N)-9*len(N),0), int(N)+1):
  temp = 0
  for ele in str(i):
    temp += int(ele)
  if int(N) == (i + temp):
    lst.append(i)
if len(lst) == 0:
  print(0)
else:
  print(lst[0])

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

이 문제는 유효범위를 줄이는 것이 시간 단축의 핵심이다.

단순히 1부터 타겟넘버 N까지 탐색한다고 하면 너무나도 많은 시간이 걸린다.

따라서 탐색의 유효범위를 구해야 하는데 이는 타겟넘버N의 자릿수와 연관이 있다.

분해합 = 타겟넘버 + 타겟넘버자릿수들의 합

분해합은 위와 같은 공식을 갖는데 타겟넘버 자릿수들의 합은 자릿수 * 9를 넘지 않는다.

예를 들어 타겟넘버가 3자리수라고 하면 타겟넘버 자릿수들의 합은 9*3 = 27을 넘지 않는다는 소리다.

따라서 우리가 탐색해야할 범위는 (타겟넘버-9*타겟넘버자릿수, 타겟넘버+1)이 되겠다.

만약 타겟넘버-9*타겟넘버자릿수 가 음수가 될 경우에는 0으로 바꿔주는 것도 잊지 말자.

따라서 (타겟넘버-9*타겟넘버자릿수, 타겟넘버+1) 범위에서 분해합 연산을 실행하여 타겟넘버와 같은 수가 있으면 그 값을 출력한다.

만약 없을 경우 해당하는 값이 없는 것이므로 문제의 조건에 맞게 0을 출력한다.