백준 2231번: 분해합 (Python)

문제

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

---

아이디어

처음에는 이걸 이분탐색으로 해야하나? 하고 접근하다 숫자와 분해합의 크기가 비례하지 않는다는것을 알고 포기했다.
그리고 브루트 포스로 접근했는데 시간을 줄이기 위해 그냥 1부터 돌리는게아니라 10 나눈 수부터 돌렸다.

근데 1부터도 가능했었다...
시간 계산을 얼추 하는 방법을 배워야 겠다.

---

제출 코드

def calc_number(val):
    result = val
    while val > 0:
        result += val % 10
        val //= 10
    return result


N = int(input())

result = 0
for curt in range(N // 10, N):
    if calc_number(curt) == N:
        result = curt
        break

print(result)