2004 조합 0의 개수 JAVA

 

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

이번 문제는 조합과 조합의 수에 대해 알아야 온전히 이해하고 풀 수 있다고 생각한다.

 

혹시, 조합식은 알지만 소인수분해에 관해 어려움을 겪고 있다면 이 문제를 풀기보다 아래의 문제를 풀어보고 이 문제를 푼다면 정말 쉽게 풀 수 있을 것이다.

 

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

1676번: 팩토리얼 0의 개수

 

 

먼저 nCm이란 조합식이다. 정의는 서로 다른 n개의 원소 중, 순서를 가리지 않고 m개의 원소를 선택하는 것을 말한다.

그럼 이 조합식을 어떻게 구할 수 있을까? 

 

조합식의 공식을 이용하자

 

조합식의 공식이다.

수학 블로그는 아니기 때문에 공식만 공유하고 넘어가겠다.

물론 고등수학에서 나오는 공식이기에 많은 분들에게 익숙할 것이다.

 

이 문제는 조합 0의 개수를 구하는 것이다.

이전 문제인 1676번의 문제에선 5의 개수만 구하였지만 이번의 경우는 다르다.

2와 5의 지수의 개수도 구해서 비교해야 한다.

 

package BJLecture.AlgoBasic1.Math;
import java.util.Scanner;
public class M2004 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long N = sc.nextLong(), M = sc.nextLong();


        int two = getPrimeFacTwo(N) -
                (getPrimeFacTwo(M) + getPrimeFacTwo(N - M));

        int five = getPrimeFacFive(N) -
                (getPrimeFacFive(M) + getPrimeFacFive(N - M));

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

    public static int getPrimeFacTwo(long N) {
        int cnt = 0;
        while(N >= 2)
            cnt += N = (N / 2);


        return cnt;
    }

    public static int getPrimeFacFive(long N) {
        int cnt = 0;
        while(N >= 5)
            cnt += N = (N / 5);


        return cnt;
    }
}