[백준/Python] 2057 팩토리얼 분해

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

2057번: 팩토리얼 분해

문제 분석

난이도

실버5

분류

수학, 브루트포스

들어가기 전에

숫자의 크기를 보고 대략적인 감을 잡을 수 있다면 정말 편하다.

문제

문제 풀이

 

풀이

입력 제한의 최댓값보다 20!이 더 큰 수이다. 즉 0~20 총 21가지에 대해 포함 / 비포함으로 탐색을 하면 된다. 그럴 경우 2^21가지 경우의 수로 200만정도로 충분히 브루트 포스로 풀어볼 수 있다.

소스코드

def bf(now,i):
    if i==21:
        return now==n
    a=bf(now+fac[i],i+1)
    b=bf(now,i+1)
    return a or b

n=int(input())
if n==0:
    print("NO")
    exit()
fac=[1,1]
for i in range(2,21):
    fac.append(fac[-1]*i)

if bf(0,0):
    print("YES")
else:
    print("NO")