BOJ 1676 팩토리얼 0의 개수 [Java]

BOJ 1676 팩토리얼 0의 개수

1. 문제 링크

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

2. 문제 해설

중고등학교 때 배웠던 수학의 기본 내용과 관련된 문제이다.
어떤 숫자 n의 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수는 n을 소인수분해 했을 때 10을 얼마나 가지고 있느냐와 같다.
10을 얼마나 가지고 있느냐는 2 x 5 쌍을 얼마나 가지고 있느냐를 의미한다.
예를 한번 들어보겠다. 240의 경우 소인수분해하면 2^4 x 3 x 5 이다. 2는 4개나 있지만 함께 짝을 맞춰줄 5는 1개 뿐이다. 즉, 2와 5를 모두 가지고 있다면 2와 5의 갯수 중 작은 값이 2 x 5 쌍의 갯수와 같다.

이제 팩토리얼에서 2 x 5 쌍의 갯수를 구하는 것을 어떻게 처리할지 생각해보자.
팩토리얼 값을 먼저 구해주고 2 x 5 쌍의 갯수를 구할 수도 있지만, 나는 팩토리얼을 구하는 과정 내에서 2 x 5 쌍의 갯수를 구해줬다.
n! = 1 x 2 x ... x n-1 x n 이다. 1은 의미가 없으니 제외하고, 2부터 시작해서 n까지 2로 나눌 수 있다면 나눠주고 2의 갯수를 늘려주고, 또 5로 나눌 수 있다면 나눠주고 5의 갯수를 늘려주는 반복문을 거치면 해결된다.
이렇게 구해준 2와 5의 갯수중 작은 값이 정답이 된다.

3. 코드 보기

import java.io.*;

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));

        int n = Integer.parseInt(br.readLine());
        int cnt2 = 0;
        int cnt5 = 0;

        for (int i = 2; i <= n; i++) {
            int a = i;

            while ((a % 2) == 0) {
                cnt2++;
                a /= 2;
            }

            while ((a % 5) == 0) {
                cnt5++;
                a /= 5;
            }
        }

        int ans = Math.min(cnt2, cnt5);

        bw.write(Integer.toString(ans));
        br.close();
        bw.flush();
        bw.close();
    }
}