백준 1010 C++ - 다리놓기

Intro

문제해결 및 소스코드

#include <iostream>

using namespace std;

/*									<문제해결>
		규칙1. 한 사이트에는 최대 한개의 다리만 연결될 수 있다.
		규칙2. 다리를 최대한 많이 지어야한다. (N개)
		규칙3. 다리끼리는 겹칠 수 없다.
		규칙4. N<=M

		직접 몇개만 그림을 그려나가다보면 규칙이 보이는 문제였다.
		서쪽에 2개의 사이트가 있고 동쪽에 M개(>=2)개의 사이트가 있을 때 M을 1씩 늘려가다보면
		(N,M = 2,2) 일 때 => 1가지 경우
		(N,M = 2,3) 일 때 => 2가지 경우
		(N,M = 2,4) 일 때 => 6가지 경우
		(N,M = 2,5) 일 때 => 10가지 경우 ... 

		그리고, N = 1 일 때는 M의 갯수에따라 경우의 수가 정해진다. (N,M = 1,1 -> 1)(N,M = 1,2 ->2)(N,M = 1,3 ->3)... (초기값설정가능)
		위 규칙에 따르면 N,M 개의 사이트가 있을 때 가능한 경우의 수는 "(N-1, M-1)의 경우 + (N, M-1)의 경우" 가 된다.
		
	*/

int dp[30][30];

int main(void)
{
	int testCase;
	cin >> testCase;

	int n, m;

	while (testCase)
	{
		cin >> n >> m;

		// .. n=1 일 때 초기값 설정
		for (int i = 1;i <= m;i++)
		{
			dp[1][i] = i;
		}

		for (int i = 2; i <= n;i++)
		{
			for (int j = 2;j <= m;j++)
			{
				if (j == i) dp[i][j] = 1;
				else
				{
					dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
				}
			}
		}

		cout << dp[n][m] << "\n";

		testCase--;
	}
	return 0;
}