[2004번] 조합 0의 개수

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 조합을 계산하는 방법

2. 조합에서의 0의 개수의 특징

조합은 다음과 같이 나타낼 수 있다.

조합에서의 0이 나타나기위한 조건은 약분 후 2의 배수와 5의 배수가 분자에 남아있으면 된다는 것이다.

즉, 1,3,6,7,9로는 어떻게 하여도 마지막 자리수가 0이 나타나지 않는다.

따라서 5!부분을 a부분이라하고, 3!부분을 b, 2!부분을 c라고 하면

a부분의 5의 개수를 모두 구하고 b,c부분의 5의 배수의 개수를 구하여 a - (b+c)를 한 후

마찬가지로 2의 배수의 개수도 구해준다.

그리하여 2의 배수와 5의 배수중 적은것을 선택하면 결과가 도출된다.

ex : 2의 배수 2개이고 5의 배수 1개이면 결국 2의 배수 하나와 5의 배수 하나가 결합되기에 최솟값을 찾는다.

소스 코드 : 

#include <stdio.h>
#define min(a,b) (a<b?a:b)
 
long long int i;
int n, r;
int five = 0, two = 0;
 
int fiveCount(int num) {
    int count = 0;
    
    for (i = 5; num / i >= 1; i *= 5)
        count += num / i;
    
    return count;
}
 
int twoCount(int num) {
    int count = 0;
    
    for (i = 2; num / i >= 1; i *= 2)
        count += num / i;
    
    return count;
}
 
int main() {
    
    scanf("%d %d", &n, &r);
 
 
    five += fiveCount(n);
    if (r != 0)five -= fiveCount(r);
    if (n != r)five -= fiveCount(n - r);
 
    two += twoCount(n);
    if (r != 0)two -= twoCount(r);
    if (n != r)two -= twoCount(n - r);
 
    printf("%d\n", min(two, five));
 
    return 0;
}