[실버 4] 1010번 다리 놓기

#include <iostream>
#include <memory.h>
using namespace std;

int memo[50][50];

int Combination(int n, int k)
{
	// 0개를 선택하거나 5개의 공에서 5개를 선택하는 경우의 수는 1.
	if (k == 0 || n == k)
		return 1;
	if (memo[n][k] != -1) 
		return memo[n][k];

	// 한번도 구한적이 없다면 계산하고 저장.
	return memo[n][k] = Combination(n - 1, k) + Combination(n - 1, k - 1);
}

int main(void)
{
	::memset(memo, -1, sizeof(memo));
	int count,west,east;
	cin >> count;

	for (int i = 0; i < count; ++i)
	{
		cin >> west >> east;
		std::cout << Combination(east, west) << std::endl;

	}
	return 0;
}

경우의 수와 n과 r이 같은 경우 1이 나올 때 조합을 떠올리자.