백준] 1010 - 다리 놓기

시간 제한 : 2초

메모리 제한 : 128MB

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

소스코드

#include <iostream>
using namespace std;
int main(void)
{
	int t, n, m;
	long long dp[31][31] = { 0, };
	cin >> t;

	for (int i = 0; i <= 30; i++)
		for (int j = 1; j <= 30; j++)
			dp[i][j] = -1;
	for (int i = 1; i <= 30; i++)
		dp[i][i] = dp[i][0] = 1;
	for (int i = 1; i <= 30; i++)
		for (int j = 1; j <= 30; j++)
			if (dp[i][j] == -1)
				dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];

	while (t--)
	{
		cin >> n >> m;
		cout << dp[m][n] << '\n';
	}
}

Tip

기본적인 동적계획법 문제로, 2차원 테이블을 활용해야 한다. DP[i][j]는 서쪽 사이트가 i개, 동쪽 사이트가 j개 있을 때의 경우의 수를 의미한다. 

if (dp[i][j] == -1)

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];