[BAEKJOON] 2004번: 조합 0의 개수 (Java)

1. 문제

nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다.

 

출력

첫째 줄에 0의 개수를 출력한다.

 

예제 입력

25 12

예제 출력

2

2. 풀이

처음 이 문제를 접근할 때 nCr = n!/(n-r)!r! 공식을 통해서 접근하려고 했다. 하지만 입력 범위가 m,n이 최대 20억인걸 보고 당연히 이 방식은 아닐꺼라고 생각했다. 그리고 끝이 0이 되려면 2x5 쌍이 1개 일 경우 뒤에 0이 한개 생기므로 2와5가 곱해진 개수를 세서 2와5의 지수 중 작은거를 선택하면 되겠다고 접근했다. 여기서 하나 더 생각해야할 것은 2와 5의 지수의 총합을 어떻게 구할지 였다.

 

100!을 생각해 봤을 때, 5가 곱해진 개수를 생각해보자. 일단 100까지의 수 중에서 5의 배수들이 5를 가지고 있음을 알고 있다. 100까지의 5의 배수는 20개 이므로 100/5=20을 먼저 구한다. 여기서 5의 지수가 2인 애들을 보면 5^2의 배수들이 5를 하나씩 더 가지고 있음을 알 수 있다 따라서 기존에 20에다가 100/5^2=4 를 더해준다.

즉, 공식으로 나타내면 다음과 같다. n보다 작은 수만큼 5를 계속 곱해줘서 n을 나눈값을 더해준다.

n!의 5의 지수승 총합 =n/5 + n/25 + n/75 + ......

2의 지수승 총합을 구하는것도 같은 원리로 생각하면 된다.

 

이제 이 원리와 nCr = n!/(n-r)!r! 공식을 이용해서 n!의 2와5의 개수를 세주고, 여기에 (n-r)!과 r!의 2와5의 지수의 총합을 빼서 둘중에 더 작은거를 선택하면 답을 구할 수 있다.

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

public class Main {

    public static long countFiveExponent(long n){

        long fiveExponent = 0;
        for (long i=5; i<=n; i*=5) {
            fiveExponent += n/i;
        }

        return fiveExponent;
    }


    public static long countTwoExponent(long n){

        long twoExponent = 0;
        for (long i=2; i<=n; i*=2) {
            twoExponent += n/i;
        }

        return twoExponent;
    }

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        long n = Long.parseLong(st.nextToken());
        long m = Long.parseLong(st.nextToken());

        long two = 0, five = 0;
        
        five = countFiveExponent(n) -countFiveExponent(n-m) -countFiveExponent(m);
        two = countTwoExponent(n) -countTwoExponent(n-m) -countTwoExponent(m);

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

}