(c++)백준 2004번: 조합 0의 개수

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

2004번: 조합 0의 개수

[풀이]

nCm = n! / m!(n-m)!이므로

n!을 구할 때 나오는 2의 개수 - m!을 구할 때 나오는 2의 개수 - (n-m)!을 구할 때 나오는 2의 개수와,

n!을 구할 때 나오는 5의 개수 - m!을 구할 때 나오는 5의 개수 - (n-m)!을 구할 때 나오는 5의 개수 중에 더 작은 수가

0의 개수가 된다. (2 * 5의 개수이기 때문!)

2020/06/18 - [백준/여러가지 문제들] - (c++)백준 1676번: 팩토리얼 0의 개수

(c++)백준 1676번: 팩토리얼 0의 개수

위의 방법대로 풀면 구해야할 값이 많기 때문에 시간초과가 난다.

따라서 2와 5의 거듭제곱으로 나누면서 개수를 세는 방법으로 풀었다.

#include <iostream>
#include <algorithm>//min
using namespace std;

int N, M;

long long get2Cnt(int num) {
	long long cnt = 0;
	for (long long i = 2; i <= num; i *= 2)
		cnt += num / i;
	return cnt;
}

long long get5Cnt(int num) {
	long long cnt = 0;
	for (long long i = 5; i <= num; i *= 5)
		cnt += num / i;
	return cnt;
}

void solution() {
	cin >> N >> M;
	long long cnt2_up = get2Cnt(N);//N!에서 2의 개수
	long long cnt5_up = get5Cnt(N);//N!에서 5의 개수
	long long cnt2_down1 = get2Cnt(M);//M!에서 2의 개수
	long long cnt5_down1 = get5Cnt(M);//M!에서 5의 개수
	long long cnt2_down2 = get2Cnt(N-M);//(N-M)!에서 2의 개수
	long long cnt5_down2 = get5Cnt(N - M);//(N-M)!에서 5의 개수
	cout << min(cnt2_up - cnt2_down1 - cnt2_down2, cnt5_up - cnt5_down1 - cnt5_down2) << '\n';
}

int main() {
	solution();
	return 0;
}