[백준][Python] 2231 분해합

분해합

접근

1부터 N까지 자연수를 순회하며
생성자의 조건에 맞게 연산한 뒤
N의 생성자를 발견한다면 반복문을 종료하고 정답으로 반환하면 된다.

다만, N의 생성자가 될 수 있는 최소값을 구해서
탐색 범위를 줄여준다면 실행 시간을 많이 줄일 수 있다.

N은 M과 M의 각 자리수의 합으로 표현 가능한 수 이다.
만약, M의 모든 자리수가 9였다면,
$N = M + (M의 길이) * 9$ 이며
따라서 $M = N - (M의 길이) * 9$ 와 같이 표현할 수 있고
이보다 작은 수는 N의 생성자가 될 수 없다.

코드

def solution(N: int):
    answer = 0
    for i in range(N-len(str(N))*9, N):
        result = i
        tmp = i
        while tmp > 0:
            result += tmp%10
            tmp //= 10
        if result == N:
            answer = i
            break
    return answer


if __name__ == '__main__':
    import sys
    N = int(sys.stdin.readline().rstrip())
    ans = solution(N)
    print(ans)