[백준 | java] 2004 조합 0의 개수

내 풀이

백준의 1676번 '팩토리얼 0의 개수' 문제와 유사하다.
조합 공식은 팩토리얼 값으로 이루어져 있기 때문에 팩토리얼 0의 개수 문제를 이용하면 쉽게 풀 수 있다. 조합 공식을 아래와 같다.

즉, n!, (n-m)!, m!의 2와 5의 승수를 구하면 0의 개수를 구할 수 있다. 2와 5의 승수를 구한 후 짝지을 수 있는 승수의 개수를 구하면 되므로 2와 5의 승수 중 최솟값을 출력하면 된다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        long n = Integer.parseInt(st.nextToken());
        long m = Integer.parseInt(st.nextToken());

        long cnt5 = five_power_n(n) - five_power_n(n-m) - five_power_n(m);
        long cnt2 = two_power_n(n) - two_power_n(n - m) - two_power_n(m);
        System.out.println(Math.min(cnt5, cnt2));

    }

    static long five_power_n (long num) {
        int cnt = 0;
        while (num >= 5) {
            cnt += (num / 5);
            num /= 5;
        }
        return cnt;
    }

    static long two_power_n (long num) {
        int cnt = 0;

        while (num >= 2) {
            cnt += (num / 2);
            num /= 2;
        }

        return cnt;
    }
}