[백준 BOJ][C++]2004번: 조합 0의 개수 풀이

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

2004번: 조합 0의 개수

 

 문제 풀이에 앞서 1676번 풀이 글을 보고 오시면 도움이 됩니다. 

 

 n, m에 대한 조합 공식은 n!/(m!(n-m)!) 입니다. 

 

 1676번 팩토리얼 0의 개수를 구할 때에는 5의 개수를 알면 0의 개수를 알 수 있었습니다. 

 

 하지만 조합 0의 개수를 구할 때에는 5의 개수 뿐만 아니라 2의 개수도 고려해야 합니다. 

 

 만약 n이 6, m이 2일 때를 봅시다. 

 

 6!의 5의 개수는 1개이고 2!과 3!의 5의 개수는 0개입니다. 5의 개수만 고려한다면 조합 0의 개수는 1개가 되겠지요. 하지만 실제로 계산해보면 15입니다. 0의 개수가 0개입니다. 10을 만들기 위해 필요한 2가 상쇄되었기 때문입니다. 

 

 따라서 각 팩토리얼의 5의 개수와 2의 개수를 따져서 총 5의 개수와 2의 개수 중 더 작은 값이 답이 됩니다.

 

#include<iostream>

using namespace std;

long long funct(int n, int k) {
	long long ans = 0;

	for (long long i = k; i <= n; i *= k) {
		ans += n / i;
	}

	return ans;
}

int main(void) {

	cin.tie(NULL);
	cout.tie(NULL);

	ios_base::sync_with_stdio(false);

	int n, m;
	long long num2, num5;
	long long ans;

	cin >> n >> m;

	num2 = funct(n, 2) - (funct(m, 2) + funct(n - m, 2));
	num5 = funct(n, 5) - (funct(m, 5) + funct(n - m, 5));

	if (num2 < num5)
		ans = num2;
	else
		ans = num5;

	cout << ans;

	return 0;
}