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

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

 

\[ _nC_r = \frac{n!}{r!(n-r)!} \]

 

뒤의 0의 개수를 구할 때에는 10의 배수가 몇개나 생기는 가가 중요합니다.  그렇기 때문에 2의 소인수의 개수와 5의 소인수의 개수가 몇개인 가가 중요하게 됩니다.  일반적으로는 2의 소인수의 개수가 더 많지만, 꼭 그렇지는 않습니다.  \(_5C_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);
}