[백준, 자바, 1676번] 팩토리얼 0의 개수

풀이

• 해당 문제를 처음에는 그냥 단순히
• 인풋으로 들어오는 값을 가지고 펙토리얼 한 값을 구한 다음 
• 10을 나누며 결과를 출력하고자 했음.
• 다만 인풋값이 500까지 들어오는 것을 보고 그대로 출력을 해보니
• 값이 계속 0으로 출력이 되어 계속 확인을 해보니
• 특정 값 이상 넘어가니 원하는 값이 나오지 않는 것을 확인.
• 이후 규칙을 찾아보려고 해도 찾기 어려워서, 수학적 힌트를 얻고자 찾아보니
• 신기하게 해당 펙토리얼의 값에서, 0인 뒷자리 개수를 알고자 한다면
• 2*5의 지수를 확인하면 되는 것 확인
• 예를 들어 10의 경우 2^1*5^1 이기에 2*5로 볼 땐 1개라 결과를 1로 출력하면 되고
• 100의 경우 2^97*5^24 이기에 2*5의 경우엔 24개이기에 24를 출력하면 됨.
• 이후 IDEA에서 입력 값을 500을 넣어도 괜찮아서 제출해보니
• 시간초과가 발생하여, DP를 활용해서 이전 값에서 특정 값의 지수만 구한 뒤
• 더하여 해당 지수를 확인하고자 하니 해결.

 

import java.util.Arrays;
import java.util.Scanner;
public class _1676 {
    static long[][] li;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        li = new long[num+1][2];
        for (int i=2; i<=num; i++) {
            fac(i);
        }
        System.out.println(Math.min(li[num][0],li[num][1]));
    }

    public static void fac(int num) {
        li[num][0] = li[num-1][0];
        li[num][1] = li[num-1][1];
        int now = num;
        while (now!=1) {
            if (now%2==0) {
                li[num][0]++;
                now/=2;
            } else if (now%5==0) {
                li[num][1]++;
                now/=5;
            } else break;
        }
    }
}