[백준] 2057번 : 팩토리얼 분해 (JAVA)

📌

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

---

📌 문제 개요

주어진 정수 N을 서로 다른 팩토리얼들의 합으로 표현할 수 있는지 판별하는 문제

- 같은 팩토리얼은 중복 사용 불가.

40321 = 8! + 1!

---

📌 접근 방법

팩토리얼은 매우 빠르게 증가한다.

20!까지만 계산하면 충분 팩토리얼 개수가 적기 때문에 큰 값부터 차례대로 빼는 그리디 전략 사용 가능.

1! = 1
2! = 2
3! = 6
...
20! ≈ 2.4e18

---

📌 핵심 아이디어

1. 1! ~ 20! 미리 계산
2. 20!부터 1!까지 내려오면서
3. N보다 작거나 같으면 한 번만 빼기
4. 최종적으로 N이 0이면 YES

팩토리얼은 배수 구조이기 때문에 큰 것부터 빼도 항상 안전하다.

---

📌 전체 코드

package no_2057;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class No2057 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long N = Long.parseLong(br.readLine());

        long[] fact = new long[21];
        fact[0] = 1;

        for (int i = 1; i <= 20; i++) {
            fact[i] = fact[i - 1] * i;
        }

        for (int i = 20; i >= 0; i--) {
            if (N >= fact[i]) {
                N -= fact[i];
            }
        }

        if (N == 0) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

---

📌 정리

• 팩토리얼 개수는 최대 20개
• 그리디로 해결 가능
• 시간복잡도는 사실상 O(1)
• long 타입 필수