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

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

2057번: 팩토리얼 분해

 

난이도 : 실버 5
태그 : 수학, 그리디 알고리즘, 브루트포스 알고리즘

 

 

설명

정수 n이 주어졌을 때, 서로 다른 팩토리얼로 나타낼 수 있으면 YES, 아니면 NO를 출력하는 문제입니다.

 

정수 145이 있습니다.

145이하의 팩토리얼 중 가장 작은 팩토리얼은 5! (5*4*3*2 = 120)입니다.

4!을 볼까요? 4*3*2 = 24로, 120 + 24 = 144로, 145보다 작으므로, 4!도 더합니다.

3!을 봅시다. 3 * 2 = 6으로, 144+6 = 150입니다. 145보다 커지므로 3!은 넘어갑니다.

2!은 2 * 1 = 2로, 144 + 2 = 146 입니다. 145보다 커지므로 2!도 넘어갑니다.

1!은 1로, 144 + 1 = 145입니다. 145와 같아졌습니다.

 

이처럼, 값을 누적하며,

지금의 값을 더했을 때, 목표 정수보다 커지면 넘어가고, 작으면 더해주는 그리디 알고리즘으로 볼 수 있습니다.

 

 

소스코드

n = int(input())

fact = [1, 1]
for i in range(2, 21):
    fact.append(fact[i - 1] * i)

sum = 0

for i in range(20, -1, -1):
    if sum + fact[i] < n:
        sum += fact[i]
    elif sum + fact[i] == n:
        print("YES")
        exit(0)

print("NO")

 

1! ~ 20! 까지 값을 구해놓고,

20부터 시작하여 위에서 말한 알고리즘을 적용합니다.

 

목표값과 같아지면 프로그램을 종료하고,

for문이 다 끝날때까지 프로그램이 살아있다면 값을 찾지 못한 것이므로 NO를 출력합니다.

 

 

n의 범위가 1 ~ 1,000,000,000,000,000,000 까지인데,

21!이 51,090,942,171,709,440,000이므로, 20!까지만 구하여 쓰면 됩니다.

 

 

후기

정수 N이 주어지면, N!을 여러개의 다른 팩토리얼로 쪼개라는 말인줄 알고,

1,000,000,000,000,000,000! 을 구하라고..? 진짜...? 하는 생각으로 머리를 싸맸는데

N!이 아니라 N을 여러개의 팩토리얼로 쪼개라는 말이였습니다.

 

항상 문제를 잘 봅시다 ㅠ.ㅠ