문제

boj1010_1 boj1010_2

N개의 사이트가 있는 서쪽에서 M개의 사이트가 있는 동쪽으로 다리를 연결하므로 N개의 다리를 지어야 한다. 이때 다리끼리는 서로 겹쳐질 수 없다는 조건이 붙었다. 이는 M개의 사이트 중 어떤 사이트에 다리를 놓을 지 정하기만 하면 순서는 알아서 정해준다는 것이다. 즉, 순서는 중요하지 않고 M개 중 N개만 고르면 되므로 조합을 사용하면 된다는 것을 알 수 있다.

조합은 조합의 정의 nCr = n! / {(n-r)! * r!}를 활용하거나 파스칼의 정리 nCr = (n-1)C(r-1) + (n-1)Cr를 사용해 구할 수 있는데, 정의를 사용하면 오버플로가 발생할 수도 있고 나눗셈 때문에 타입 변환도 해줘야 하므로, 파스칼의 공식을 사용해 풀어보았다.

int comb(int n, int r) {
	if (n == r || r == 0) return 1;
	else return combination(n - 1, r - 1) + combination(n - 1, r);
}

그런데 조합을 재귀로 푸니까 시간이 너무 오래 걸린다. DP를 이용해 값들을 메모해 놓으면 훨씬 더 빠르게 답을 구할 수 있다.

구현

#include <iostream>
#define MAX 31
using namespace std;

int combination[MAX][MAX];

/* recursion too slow
int comb(int n, int r) {
	if (n == r || r == 0) return 1;
	else return combination(n - 1, r - 1) + combination(n - 1, r);
}
*/

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int T, N, M, i, j;
	cin >> T;

	for (i = 0; i < MAX; i++) combination[i][0] = 1;
	for (i = 1; i < MAX; i++) combination[i][1] = i;
	for (i = 2; i < MAX; i++) {
		for (j = 2; j <= i; j++) combination[i][j] = combination[i - 1][j - 1] + combination[i - 1][j];
	}

	while (T--) {
		cin >> N >> M;
		cout << combination[M][N] << "\n";
	}
	return 0;
}