[백준] 3474 교수가 된 현우 [java]

문제

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

시간 초과

주어진 n의 n!의 오른쪽 끝에 있는 0의 갯수를 구하면 된다.
쉽게 생각하면, n! 수를 모두 탐색하면서 2와 5의 갯수를 구하면 될 것 같다.
ex) 10! --> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10을 모두 확인하며 2와 5의 총 갯수를 센다.

하지만 주어지는 n의 최댓값이 10억이므로, 만약, 10억이 입력되면 1부터 10억까지 반복문을 돌며 2와 5의 갯수를 세야 하는 일이 생긴다 --> 시간초과

풀이

만약 n이 60이라고 생각해보자.
일단 60 이하의 5의 배수를 나열해보자.
5 10 15 20 25 30 35 40 45 50 55 60 -> 일단 5가 1개 포함된 경우는 12개이다. 그리고 25 50은 5가 2개 포함돼있다. -> 5가 1개 포함된 수의 갯수, 2개 포함된 수의 갯수, 3개 포함된 수의 갯수... 를 세면 된다.
2도 똑같다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int tCase = Integer.parseInt(bufferedReader.readLine());

        for(int i = 0; i < tCase; i++){
            int num = Integer.parseInt(bufferedReader.readLine());

            int two = 0, five = 0;

            for(int j = 2; j <= num; j *= 2){
                two += num / j;
            }
            for(int j = 5; j <= num; j *= 5){
                five += num / j;
            }

            System.out.println(Math.min(two, five));
        }
    }

}