[Python] 백준 2231번 분해 합(완전 탐색)

문제

풀이

완전 탐색이지만 조금 더 신경을 쓰기로 했다.

문제의 조건 중에서 N은 1,000,000을 넘기지 않는다. 그렇기에 대충 어림잡아 자릿수의 합이 최대인 999,999를 생각해 보면, 999,999를 생성자로 가지는 수는 999,999+54(9*자릿수)=1,000,053 이다. 즉, 한 숫자의 생성자가 무슨 수 인지 찾으려면 최대 54개의 숫자만 검사하면 된다는 뜻이다.

(실제로는, N의 최댓값인 1,000,000은 생성자를 가지지 않고, 999,999는 생성자를 가지는데, 999,999의 생성자는 999,954 이다. 즉 999,999 - 999,954= 45, 최대 45가지의 숫자만 검사하면 된다. 하지만 실제 코딩 테스트에서 45와 54는 큰 차이가 없고, 54를 떠올리는 것이 더 빠르니 그냥 이렇게 하자.)

따라서 N이 주어지면 N-54부터 N까지 for문으로 생성자가 있는 지, 없는 지를 검사하면 된다.

n = int(input())

if n <= 54:

    for i in range(1, n+1):

        num = i+sum([int(j) for j in str(i)])

        if num == n:

            print(i)

            exit(0)

else:

    for i in range(n-54, n):

        num = i+sum([int(j) for j in str(i)])

        if num == n:

            print(i)

            exit(0)

print(0)