[C/C++ 백준 2004번] 조합 0의 개수 (Silver 2)

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

2004번: 조합 0의 개수

그냥 습관처럼 5의 개수만 구해서 출력했는데, 틀렸습니다가 떠서 당황했다. 혹시 자료형때문인가 해서 long long으로 바꾸었는데, 알고보니 5C1과 같은 경우를 고려 안했다. 그래서 2의 개수도 구해 min을 때려주면 끝.

핵심은 nCm=n!/(n-m)!m! 에서 1 ~ n, 1 ~ n-m, 1 ~ m 각각의 5의 개수와 2의 개수를 구하는 것이다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
	long long int n, m, cnt1=0, cnt2=0, cnt3=0;
	long long int tcnt1=0, tcnt2=0, tcnt3=0;
	scanf("%lld %lld", &n, &m);
	long long int i=5, j=2;
	while(i<=n){
		cnt1 += n/i;
		i *=5;
	}
	while(j<=n){
		tcnt1 += n/j;
		j *=2;
	}
	i=5;
	j=2;
	while(i<=m){
		cnt2 += m/i;
		i *= 5;
	}
	while(j<=m){
		tcnt2 += m/j;
		j *=2;
	}
	i=5;
	j=2;
	while(i<=n-m){
		cnt3 += (n-m)/i;
		i *= 5;
	}
	while(j<=n-m){
		tcnt3 += (n-m)/j;
		j *=2;
	}
	printf("%lld",min(cnt1-cnt2-cnt3,tcnt1-tcnt2-tcnt3));
}