[백준] 2057 팩토리얼 분해

Problem Solving/Baekjoon

[백준] 2057 팩토리얼 분해 - Greedy / Java

graycode 2023. 5. 10. 20:04

• 문제 링크

2057번: 팩토리얼 분해

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

www.acmicpc.net

• 풀이 과정

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long n = Long.parseLong(br.readLine());

        bw.write(n != 0 && isPossible(n) ? "YES" : "NO");
        bw.flush();
    }

    private static boolean isPossible(long n) {
        long fact = 2432902008176640000L;

        for (int i = 20; i > 0; i--) {
            fact /= i;
            if (n >= fact)
                n -= fact;
        }

        return n == 0;
    }

}