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

문제

2004번: 조합 0의 개수

---

접근 방법

1. n! / (m-n)! * m! 를 구할때 끝자리 0 의 개수를 출력하는 문제입니다.

2. 그렇다면 소인수 분해를 하고 곱했을때 0이 되는 수인 2와 5에 대해서 따져보면 됩니다.

3. 2와 5중 둘중 작은 수를 구하면 그것이 0의 개수가 됩니다. ex) 2^2 * 5^2 =  100 , 2^3 * 5^2 = 200

 

코드

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

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static long N,M;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());

        N = Long.parseLong(st.nextToken());
        M = Long.parseLong(st.nextToken());
    }
    
    //5 개수 세기
    public static long cnt5(long input){
        long temp = 0;
        while(input >= 5){
            temp += input/5;
            input /=5;
        }
        return temp;
    }

    //2 개수 세기
    public static long cnt2(long input){
        long temp = 0;
        while(input >= 2){
            temp += input/2;
            input /=2;
        }
        return temp;
    }

    //실행
    public static void process() {
        long countFive = cnt5(N) - cnt5(N-M) - cnt5(M);
        long countTwo = cnt2(N) - cnt2(N-M) - cnt2(M);

        System.out.println(Math.min(countFive,countTwo));
    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}