[백준] 2004 - 조합0의개수 (JAVA)

조합의 성질을 이용하는 문제이다.
nCr = n! / r! * (n-r)! 이므로 n!에서 사용된 2와 5의 개수를 더하고, r!과 (n-r)!에서 사용된 2와 5의 개수는 빼주면 된다.

범위가 최대 20억이므로 팩토리얼값을 직접 구하면 안된다.또, 1부터 20억까지 모두 완전탐색을 하는 경우도 시간초과가 난다. (1억이상을 완탐하는 경우는 거의 시간초과가 난다고 봐야한다고 한다.)

결국 구글링을 했는데 배운내용을 차근차근 정리해보겠다
예를 들어 63!의 5의 개수를 구한다고 해보자.
5의 개수를 구하기전에 63!에 있는 5의"배수"의 개수를 먼저 구해보자.
63! = 63*62*61* ... * 3*2*1로 이때 5의배수의 개수를 구하려면 63/5 = 12개이다.
오른쪽항 중에서 5로 나누어떨어지는 것들만 모으면 60*55*50*...*10*5가 된다.
그렇다면 이 5의배수들을 5로 계속 나누면 원하는 5의배수의 전체 개수가 나올 것이다. 전체 63개를 다 조사할 필요가 없이 위의 12개의 숫자만 살피면 되는것이다.

따라서 다시 5로 나누면, 12*11*10* ...* 2*1이고, cnt5+= (63/5) 이다.
이를 또 다시 반복하면 2*1이 되고 cnt5+= (12/5)이다. 따라서 63!의 5의배수 개수는 14개이다.

이와 같은 방식으로 소인수를 구할 수 있다. 코드로 표현하면 다음과 같다.

import java.io.*;

import static java.lang.Math.min;

public class No2004_조합0의개수 {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s[] = br.readLine().split(" ");
        int N = Integer.parseInt(s[0]);
        int M = Integer.parseInt(s[1]);

        long cnt2 = count2(N) - count2(M) - count2(N-M);
        long cnt5 = count5(N) - count5(M) - count5(N-M);


        System.out.println( min(cnt2,cnt5));
      
    }

    public static long count5(int num) {
        long temp =0;
        if (num<5) return 0;
        for (long i=5;i<=num;i=i*5) {
            temp= temp+ (num/i);
        }
        return temp;
    }

    public static long count2(int num) {
        long temp =0;
        if (num<2) return 0;
        for (long i=2;i<=num;i=i*2) {
            temp=temp+ (num/i);
        }
        return temp;
    }

}

느낀점

고등학교때 수학 더 열심히 할걸