[python]백준 2231번: 분해합

Problem

문제링크: www.acmicpc.net/problem/2231
알고리즘 : 브루트포스
입력 - N(1 ≤ N ≤ 1000000)
출력 - 가장 작은 생성자

---

solution

1부터 N 까지 탐색을 하는 방법도 있지만 N - 9(각 자릿수가 가질수 있는 최댓값) * 자릿수 부터 N 까지만 조사하는 방법이 더욱 빠르다.

N = int(input())
start = max(N - (len(str(N)) * 9), 0)
result = 0
for i in range(start, N+1):
    case = i + sum(list(map(int, str(i))))
    if case == N:
        result = i
        break
print(result)