다리 놓기 (feat. 백준, 1010번)

다리 놓기
https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1010
#include <iostream>
using namespace std;
inline unsigned long long factorial(register int n, register int k) {
	if (n == k || n < 2)
		return 1;
	return n * factorial(n - 1, k);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N;
	cin >> N;
	for (register int i = 0, x, y, n, k; i < N; ++i) {
		cin >> x >> y;
		n = max(x, y), k = min(x, y);
		if (k > (n - k))
			cout << factorial(n, k) / factorial(n - k, 1) << endl;
		else
			cout << factorial(n, n - k) / factorial(k, 1) << endl;
	}
	return 0;
}
// *&)*@*

 

1. 문제는 결국 N개중 M개의 조합을 구하는 것을 묻고 있습니다.
2. 조합은 nCk (n >= k). 즉, n! / (k! * (n - k)!) 입니다. 하지만 문제에서 주어진 팩토리얼의 범위가 최대 30까지인데, 이는 unsigned long long의 자료형을 벗어나는 아주 큰 수입니다.
3. n! / (k! * (n - k)!) 는 두 가지로 변경하여 풀이할 수 있습니다. 첫째는 n * n-1 * n-2 * ... * n-k / (n-k)! 입니다. 분모의 k!는 분자의 n!과 겹치는 부분이 생기기 때문입니다. 둘째는 n * n-1 * n-2 * ... * n - (n - k) / k! 입니다. 분모의 (n-k)!는 분자의 n!과 겹치는 부분이 생기기 때문입니다.
4. 따라서 k와 n-k를 비교했을때, k가 더 크다면 위 처음 수식을, n-k가 더 크다면 위 두번째 수식을 사용하여 팩토리얼로 계산되는 과정을 최소화 시킬 수 있습니다.