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

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

2004번: 조합 0의 개수

 

10 = 2 * 5에서, 2와 5의 승수만을 고려하여 풀 수 있다는 아이디어를 내야한다.

nCr = n! / (r! * (n-r)!)의 각각의 팩토리얼에서 2, 5의 승수를 가져와서 연산을 해주면 된다. 예를 들어, 5C3 = 5!/(3!*2!) = (1*2*3*4*5) / ((1*2*3) * (1*2))에서 5!, 3!, 2!에는 각각 2^1, 5^1 / 2^1 / 2^1가 포함되며 2^(-1), 5^0이므로 0의 개수가 0이다. 만약 어떤 조합에서 2^3, 5^2가 나왔다면 그것의 0의 개수는 2개일 것이다.

이것을 일반화하여 n!에서 p의 승수를 구하는 함수를 작성하면 다음과 같은 코드가 나온다.

// n!에서 p의 승수를 구한다
int get_power(int n, int p) {
	int res = 0;

	while (n >= p) {
		res += n / p;
		n /= p;
	}

	return res;
}

특정 조합으로부터 p의 승수를 구할 수도 있다.

int get_power_from_combination(int n, int m, int p) {
	return get_power(n, p) - get_power(m, p) - get_power(n - m, p);
}

 

마지막으로 위 함수를 2, 5에 대해서 써주면 바로 이 문제를 풀 수 있다.

전체 코드는 아래와 같다.

 

#include <iostream>
using namespace std;

// n!에서 p의 승수를 구한다
int get_power(int n, int p) {
	int res = 0;

	while (n >= p) {
		res += n / p;
		n /= p;
	}

	return res;
}

int get_power_from_combination(int n, int m, int p) {
	return get_power(n, p) - get_power(m, p) - get_power(n - m, p);
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int n, m;
	cin >> n >> m;

	cout << min(get_power_from_combination(n, m, 2), get_power_from_combination(n, m, 5));

	return 0;
}