백준 2004 조합 0의 개수[Java]

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

풀이

정수론 및 조합론의 이전 문제인 팩토리얼 0의 개수의 풀이를 응용하면 된다.
팩토리얼 0의 개수를 구할 때는 5의 개수만 구하면 됐지만, 이번 문제는 2의 개수도 따로 구해주어야 한다.

코드

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

public class Main {

    public static int division(int n, int div) {
        int cnt = 0;

        while (n >= div) {
            cnt += n / div;
            n /= div;
        }
        return cnt;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = a - b;

        int two = 0, five = 0;

        two += division(a, 2);
        five += division(a, 5);

        two -= (division(b, 2) + division(c, 2));
        five -= (division(b, 5) + division(c, 5));

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

    }
}

• nCr = n! / r!(n-r)!
• 위의 공식을 사용하여 nCr을 소인수분해 했을 때 2의 개수와 5의 개수를 따로 구한다.
• 그 다음 두 수 중 최솟값을 출력한다.

참고: 백준 1676 팩토리얼 0의 개수 알고리즘 설명 글