백준 3474 교수가 된 현우(JAVA)

문제 설명

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

 

풀이과정

 N! 에서 오른쪽 0의 개수를 구하기 위해서는 10의 배수가 몇개인지 알아내면 된다. 10은 2와 5의 곱으로 만들어지기 때문에 N!에 2와 5가 몇개씩 포함되어 있는지 구한 후 둘 중 더 작은 값을 출력하면 된다.

 

 N! 에서 2와 5의 개수를 어떻게 셀 수 있는지에 대한 풀이이다. 위 사진처럼 (N / 2) + (N / 2^2) + (N / 2 ^ 3) 이런식으로 2의 개수를 카운팅 할 수 있고, 5의 개수도 동일하게 구하면 된다.

 

정답코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//        StringTokenizer st = new StringTokenizer(br.readLine());

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());

            int twoCnt = 0;
            int fiveCnt = 0;

            for (int j = 2; j <= N; j *= 2) {
                twoCnt += N / j;
            }

            for (int j = 5; j <= N; j *= 5) {
                fiveCnt += N / j;
            }

            bw.write(Math.min(twoCnt, fiveCnt) + "\n");
        }

        bw.flush();
    }
}