[JAVA] 백준 팩토리얼 0의 개수 1676

 

문제의 요점은 n이 커지면서 팩토리얼의 값을 변수에 저장할 수 없다는 것이다.

그럼 고민해봐야할게 어떨 때 숫자가 0으로 끝나는지 고민해봐야한다. 
차근 차근 10부터 50, 100, 150, 1500, 10000, 
0으로 끝나는 숫자들을 확인해보면 1*10, 5*10, 15*10, 15*10*10, 10*10*10*10 인것을 알 수 있다. 
즉 문제의 답은 해당 숫자에 10이 얼마나 들어가 있는지 확인해보면 된다, 
그럼 각 반복문을 돌면서 10으로 나눠 떨어진다면 10으로 계속 나눠주고 count를 해주면 될까? 



안된다. 왜냐하면 10은 2 * 5의 구성으로도 가능하기 때문이고 팩토리얼은 연속된 숫자들의 곱으로 이전 값에 영향을 받는다, 따라서 해당 숫자가 10으로 나눠 떨어질때까지 반복하고 5로 나눠질때까지 반복하고 2로 나눠질때까지 반복한 후 10으로 나눠떨어진 개수와 (5로나눠 떨어진 개수와 2로 나누어 떨어진 개수) 중 작을 것을 합하면 답을 구할 수 있다.

왜 2와 5는 나누어 떨어진 개수중 작은 것을 선택해야할까? 10은 2와 5의 구성으로 되어있는데 10이 구성되기 위해선 2와 5 둘다 필요하기 때문에 더 작은 개수를 택해야 한다.

 

import java.io.*;

public class 팩토리얼0의개수1676 {
    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw =new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int tenAnswer =0;
        int twoAnswer = 0;
        int fiveAnswer = 0;
        for(int i =1; i<=n; i++){
            int temp = i;
            while (temp%10 ==0){
                temp /=10;
                tenAnswer++;
            }
            while (temp%5 ==0){
                temp /=5;
                fiveAnswer++;
            }
            while (temp%2 ==0){
                temp /=2;
                twoAnswer++;
            }
        }
        int answer = tenAnswer + Math.min(twoAnswer, fiveAnswer);
        bw.write(answer+"");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

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