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

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

2057번: 팩토리얼 분해

 

[레벨]

- Silver 5

 

[알고리즘]

- 부르트 포스

- 수학

 

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long N = Long.parseLong(br.readLine());
        long[] arr = new long[21];
        if (N == 0) {
            System.out.println("NO");
            return;
        }

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

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

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

 

[풀이]

N의 범위가 20! 까지이기 때문에 전체적으로 long 으로 초기화해준다.

N이 0일 경우 바로 NO를 출력해준다.

 

1. N을 20! 부터 0!까지 차례로 빼본다.

2. N >= arr[i]일 경우 N-=arr[i]을 한다.

3. 반복 후 N이 0일 경우 YES 아닐경우 NO를 출력한다.