BOJ_2057 : 팩토리얼 분해

👉 문제링크

2057번: 팩토리얼 분해

---

---

🔸 문제 분석 🔸

• 팩토리얼의 조합으로 n을 만들 수 있는지 판단한다.
  • n보다 작은 팩토리얼을 큰 수부터 n을 빼며 0을 만들 수 있는지 확인한다(그리디)

🔸 코드 🔸

fact = [0] * 20
fact[0] = 1
for i in range(1, 20):
    fact[i] = fact[i-1] * i

n = int(input())

if n == 0:
    print("NO")
else:
    for i in range(19, -1, -1):
        if n >= fact[i]:
            n -= fact[i]
    if n:
        print("NO")
    else:
        print("YES")

🔸 코드 해석 🔸

• n의 최대값 1,000,000,000,000,000,000은 fact(19)보다 크고, fact(20)보다 작으므로, fact(19)부터 n에서 빼며 계산한다.
• 팩토리얼의 최소값 fact(0)은 1이므로 n이 0이면 만들 수 없다.

---

🔸 end 🔸

• 팩토리얼 19가 그렇게 크지 않을거라 생각했는데, 값을 보고 놀랐던 것 같다.
• 만들 수 있는지 없는지 빼며 계산하는 것이 아주 그리디한 풀이라고 느꼈다.
• 팩토리얼의 조합을 모두 계산하는 Brute Force 알고리즘으로도 풀이되는 것 같다.