[C/C++] 백준 #2004 조합 0의 개수(수학)

조합을 계산할 때에는 보통 다음의 식을 사용합니다.

 

$${}_n{C}_r=\frac{n!}{r!(n-r)!}$$

 

뒤의 0의 개수를 구할 때에는 10의 배수가 몇개나 생기는 가가 중요합니다.  그렇기 때문에 2의 소인수의 개수와 5의 소인수의 개수가 몇개인 가가 중요하게 됩니다.  일반적으로는 2의 소인수의 개수가 더 많지만, 꼭 그렇지는 않습니다.  ${}_5{C}_1$의 경우라면 5의 소인수의 개수는 1개, 2의 소인수의 개수는 0개이니까요.  그래서 소인수를 카운팅할 때, 2의 소인수 개수와 5의 소인수 개수를 같이 카운팅해주어야 합니다.

 

Trailing Zero's

 

$n!$의 경우라면 뒤에 연속으로 나오는 0의 개수를 세기 위해서라면 5의 소인수의 개수를 세면 됩니다.  5로 계속 나눈 몫의 합을 구하면 뒤에 연속으로 나오는 0의 개수를 쉽게 셀 수 있습니다.  $100!$을 직접 구하려면, 큰수 곱셈을 구현하지 않는다면 구하기 어렵습니다.  하지만 뒤에 나오는 연속된 0의 개수는 20+4=24로 손쉽게 구할 수 있습니다.  20은 100을 5로 나눈 몫이고, 4는 20을 5로 나눈 몫입니다.

 

이 방법을 이용해서 2의 소인수의 개수와 5의 소인수의 개수를 구한 후에 둘 중 소인수의 수가 적은 것이 조합에서 뒤에 나오는 연속된 0의 개수가 됩니다.

 

제가 작성한 소스입니다

//------------------------------------------------
//    baekjoon #2004 - Trailing Zeros Counting of Combination
//        - by Aubrey Choi
//        - created at 2019-06-27
//------------------------------------------------
#include <stdio.h>

int main()
{
    int n, k, t, f = 0, s = 0;
    scanf("%d%d", &n, &k);
    t = n/5; while(t) { f += t; t /= 5; }
    t = (n - k) / 5; while(t) { f -= t; t /= 5; }
    t = k/5; while(t) { f -= t; t /= 5; }
    t = n / 2; while(t) { s += t; t /= 2; }
    t = (n - k) / 2; while(t) { s -= t; t /= 2; }
    t = k / 2; while(t) { s -= t; t /= 2; }
    printf("%d\n", f<s?f:s);
}