문제

문제 출처

문제 해결 전략

조합으로 계산해야 한다는 사실을 알 수 있다. 그러므로 Combination을 이용하면 되는데 combination만을 이용하면 시간초과가 뜨기 때문에
nCm = n-1Cm-1 + n-1Cm
공식을 이용해준다!

코드

#include<iostream>
#include<cstring>
using namespace std;
int dp[31][31];

int bridge(int m, int n)
{
	if (m == n || n == 0)
		return 1;
	if (dp[m][n])return dp[m][n];
	return dp[m][n] = bridge(m - 1, n - 1) + bridge(m - 1, n);
}
int main()
{
	int t,n,m;
	cin >> t;
	
	for (int i = 0; i < t; i++)
	{
		cin >> n >> m;
		memset(dp, 0, sizeof(dp)); //dp 초기화
		cout << bridge(m, n) << endl;
	}
}