[백준 13600번 / Java] Fatorial

문제 링크

Silver 1

 

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

13600번: Fatorial

 

 

---

 

 

풀이

solved.ac를 따라 class만 풀다보니 완전탐색만 너무 많이나와서 실2 ~ 실1기준 DP, 그리디를 좀 풀어보고 골랜디를 하기로했다. 한 4~5문제만 풀고 골랜디를 시작할 예정.. - 잡담 -

 

 

DP를 이용해 팩토리얼 수를 구하고, 문제 조건에서 N 이상의 수는 필요없었기 때문에

팩토리얼 수의 값이 N을 넘는 순간 break를 걸어주었다.

반대로 큰 수부터 탐색하여 최적의 해를 구했음.

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

public class BaekJoon13600 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] factorial = new int[N + 1];
        factorial[0] = 0;
        factorial[1] = 1;

        int tmp = 0;
        for(int i = 2; i <= N; i ++) {
            factorial[i] = factorial[i - 1] * i;
            if(factorial[i] > N) {
                tmp = i;
                break;
            }
        }

        int cnt = 0;
        for(int i = tmp; i >= 1; i --) {
            int div = 0;
            if(N / factorial[i] > 0) {
                div = N / factorial[i];
                N %= factorial[i];
                cnt += div;
            }

            if(N == 0) {
                System.out.println(cnt);
                return;
            }
        }
    }

}