[Python/파이썬] 백준 2057번 팩토리얼 분해

https://www.acmicpc.net/problem/2057

코드

n = int(input())

factorial = [1]
for i in range(1, 20):
    factorial.append(factorial[-1]*i)

answer = "NO"


def bt(num, total):
    global answer
    if total == n:
        answer = "YES"
        return
    elif total > n or num >= 20:
        return
    # num을 포함
    bt(num+1, total+factorial[num])
    # num을 포함X
    bt(num+1, total)


if n != 0:
    bt(0, 0)
print(answer)

 

문제에 주어진 N의 범위를 처음 봤을 때는 어떻게 해야 할지 막막했는데, 생각해보니 N의 범위를 넘는 팩토리얼 수가 그렇게 많지 않을 것 같았다. 그래서 확인해보니 20!만 해도 이미 1,000,000,000,000,000,000보다 크다. 그렇기에 0~19까지의 팩토리얼 수를 사용하여 만들 수 있는지 없는지를 판별하면 된다.

 

그리고 해당 문제에서는 서로 다른 M개의 팩토리얼의 합으로 N을 만들 수 있냐고 물어봤기 때문에 0-1 knapsack 문제처럼 백트래킹을 이용하여 0~19까지의 수를 포함할지 안 할지 2가지 선택지로 나누어서 백트래킹을 진행하면 된다. 최악의 경우는 2^20이지만 가지치기를 통해 그보다 훨씬 적은 연산으로 답을 구할 수 있다.