백준 알고리즘 2231 (분해합) - python

[문제] 백준 알고리즘 2231 (분해합)

> https://www.acmicpc.net/problem/2231

2231번: 분해합

 

문제 이름은 분해합이지만, 사실 분해합의 반대 프로세스인 생성자를 구하는 문제이다.

브루트 포스(무차별 대입)를 해야하는 만큼, 효율적인 방법을 강구해봤다.

 

n보다 작은 수를 다 조사하는 것이 아니라, 생각해보니 효율적인 for문 범위를 생각할 수 있다.

예로 나온 256 = 245 + 2 + 4 + 5 으로 설명하면, 

256 = 245(본인) + 2(첫째자리) + 4(둘째자리) + 5(셋째자리)로 생각할 수 있다.

반대로 생각하면, 245(본인) = 256 - ( 2(첫째자리) + 4(둘째자리) + 5(셋째자리) ) 이다.

어떤 자리든 한 자리는 최대 9의 수를 가지므로, 256 - 3(세자리) * 9(최대) = 229 부터 255 까지만 검사해도 된다!

따라서, 먼저 len(str(n))을 조사해서, for문의 최소 범위를 조절해주면 아주 효율적인 방법이 된다.

여기서, 최소 범위가 1이하가 되면 안되므로, if문을 이용해서 1이상이 되도록 한다.

각 자릿수의 합은 str과 map, sum을 활용해서 간단히 구현했다.

 

[Code]

import sys
def solve(n):
    _min = n - len(str(n)) * 9
    _min = 1 if _min < 1 else _min
    for i in range(_min, n):
        _sum = i
        _sum += sum(map(int, str(i)))
        if _sum == N:
            print(i)
            return
    print(0)

N = int(sys.stdin.readline())
solve(N)