백준 1010번: 다리 놓기

백준 온라인 저지(BOJ) 1010번 문제

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

1. 문제 요약

강의 서쪽에 N개, 강의 동쪽에 M개의 구역이 있다. (N <= M)

구역끼리 1대 1로, 다리끼리 겹쳐지지 않게 다리를 지을 때 가능한 경우의 수는?

2. 알고리즘

강의 동쪽에 있는 M개의 구역 중 N개를 고르는 경우의 수를 구하는 문제이다. 당연히 조합이다.

3. 코드

#include <iostream>

long long c(int n, int r) {
	static long long mem[30][30] = { 0 };
	if (mem[n][r] > 0) return mem[n][r];
	if (r == 0 || n == r) return mem[n][r] = 1;
	return mem[n][r] = c(n - 1, r - 1) + c(n - 1, r);
}

int main() {
	int T;
	scanf("%d", &T);
	for (int i = 0; i < T; ++i) {
		int N, M;
		scanf("%d %d", &N, &M);
		printf("%lld\n", c(M, N));
	}

	return 0;
}