[Python]백준_2057 : 팩토리얼 분해

출처

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

---

문제

음 아닌 정수 N이 주어졌을 때, 이 수를 서로 다른 정수 M(M ≥ 1)개의 팩토리얼의 합으로 나타낼 수 있는지 알아내는 프로그램을 작성하시오. 예를 들어 2=0!+1!로 나타낼 수 있지만, 5는 이와 같은 방식으로 나타낼 수 없다.

입력

첫째 줄에 정수 N이 주어진다.

출력

입력으로 주어진 수를 서로 다른 정수 M개의 팩토리얼의 합으로 나타낼 수 있으면 YES, 없으면 NO를 출력한다.

제한

• 0 ≤ N ≤ 1,000,000,000,000,000,000

---

예제 입출력

---

알고리즘 분류

• 수학
• 그리디 알고리즘
• 브루트포스 알고리즘

---

➡️문제 분석

큰 팩토리얼부터 살펴보면서 그 값이 n보다 작으면 변수 sum에 더해주고 크면 넘어가는 식으로 반복해서 누적합 sum이 n과 같아지는지 비교해본다.

---

➡️코드(⭕)

n = int(input())

# 1! ~ 20! 까지 값을 구함
fact = [1, 1]
for i in range(2, 21):
    fact.append(fact[i-1]*i)

sum = 0

for i in range(20, -1, -1):
    # 20!부터 살펴보면서 팩토리얼 누적 합을 구함
    if sum+fact[i] < n:
        sum += fact[i]
    elif sum+fact[i] == n:      # 누적 합이 정수 n과 같은 경우
        print("YES")
        exit(0)

print("NO")

---

➡️코드 분석

1. 정수 n의 범위의 최댓값은 21!을 넘지 않으므로 20! 까지만 구하여 fact 안에 넣어준다.

2. 20!부터 n보다 작은 범위인지 판단해준다.

3. sum+k!이 n보다 작으면 sum에 더해주고, 크면 (k-1)!을 보는 식으로 반복을 진행해준다.

4. 그러다 sum이 정수 n과 같아지는 경우 YES를 출력하고, 반복문을 끝까지 돌렸는데도 n와 같아지는 경우가 없으면 NO를 출력한다.

---

➡️end

나는 큰 팩토리얼부터 비교해봤는데 작은 팩토리얼부터 하는 분들도 있었다.