다리 놓기

DP 문제로 정해진 규칙을 활용해 메모이제이션으로 해결했다.

#include <iostream>
using namespace std;

int d[50][50];

int checking(int n, int m) {
	if (d[n][m] > 0) return d[n][m];
	if (n == m) return d[n][m] = 1;
	else if (n > m) {
		return d[n][m] = 0;
	}
	else if (n == 1) {
		return d[n][m] = m;
	}
	else {
		for (int k = m - 1; k >= n - 1; k--) {
			d[n][m] += checking(n-1, k);

		}
		return d[n][m];
	}
}


int main()
{
	int tc;
	cin >> tc;

	for (int T = 1; T <= tc; T++) {
		int n, m;
		cin >> n >> m;

		cout<<checking(n, m)<<'\n';
	}
	return 0;
}