BOJ 2004 조합 0의 개수 [Java]

BOJ 2004 조합 0의 개수

1. 문제 링크

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

2. 문제 해설

어떤 숫자 n의 끝자리 0의 개수는 n을 소인수분해 했을 때 10을 얼마나 가지고 있느냐와 같다.
10을 얼마나 가지고 있느냐는 2 x 5 쌍을 얼마나 가지고 있느냐를 의미한다.
소인수분해를 했을 시 2와 5를 모두 가지고 있을 때, 2와 5의 갯수 중 작은 값이 2 x 5 쌍의 갯수와 같다.

nCm = n! / (r! x (n - r)!) 이다. 우리는 조합의 값을 구할 필요는 없다. 단지 2와 5의 갯수만 구하면 정답을 구할 수 있다.
n! / (r! x (n - r)!) 에서 2의 갯수를 어떻게 구할 수 있을까?
n! / (r! x (n - r)!) 의 2의 갯수 = n!에 있는 2의 갯수 - r!에 있는 2의 갯수 - (n - r)!에 있는 2의 갯수 이다.
5의 갯수도 같은 방식으로 구할 수 있다.

그렇다면 a!내의 b의 갯수를 구할 수 있다면 정답을 쉽게 구할 수 있다. 그러므로 a!내의 b의 갯수를 구하는 메서드를 구현해보자.
예로 71! 을 소인수 분해했을 때 5가 몇 개 있는지를 구하는 과정을 들어보겠다. 71! = 71 x 70 x ..... x 2 x 1 이다.
이 중 5의 배수는 몇 개일까? 71 / 5 = 14개이다. 14개 이 외의 수들은 5를 소인수로 가지고 있지 않다.
이때의 14개의 수를 나열해보면, 70 x 65 x ... x 10 x 5 이다.
14개의 5의 갯수를 저장해주고, 각각의 14개의 수들을 5로 나눠보면, 14 x 13 x ... x 2 x 1 이 된다.
여기에서 5의 배수의 개수는 14 / 5 = 2개가 된다. 이런 방식을 통해, 71! 안에는 5가 총 16개가 있다는 것을 알 수 있다.
위와 같은 방식으로 a!내의 b의 갯수를 구하는 메서드를 작성하였다.

3. 코드 보기

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 n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int cnt2 = getCnt(n, 2) - getCnt(m, 2) - getCnt(n - m, 2);
        int cnt5 = getCnt(n, 5) - getCnt(m, 5) - getCnt(n - m, 5);

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

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

    static int getCnt(int a, int b) { // a!를 소인수분해 했을 때, b의 갯수를 구하는 메서드
        int cnt = 0;

        while (a >= b) {
            cnt = cnt + (a / b);
            a /= b;
        }

        return cnt;
    }
}