BaekJoon 1010 다리놓기

Link https://www.acmicpc.net/problem/1010

소스결과 1988 KB 16ms

출처 BackJoon 

언어 C++ 17

분류 다이나믹 프로그래밍

 

설명

만들 수 있는 다리의 총 합을 구하는 문제

DFS 처럼 생각해서 가지치기를 했더니 최대 다리 개수를 놓았을 경우에 너무 오래 걸렸다.

 

점화식은 간단하다

RES[i][j] = RES[i-1][j] + RES[i][j-1]

예외 조건은 순서가 역전 되지 않게 만들어 주기만 하면 된다.

 

어렵게 생각하면 밑도 끝도 없이 어렵다.. 간단하게 생각하자

 

알고리즘

1. DP Table을 초기화한다. 

2. 입력값 n, m 에 대하여 DP Table [ n -1 ] [ m - 1 ] 을 출력한다.

 

소스코드 

#include <iostream>

using namespace std;

const int MAX = 30;

int dp[MAX][MAX + 1];

int main()
{
	int n;

	cin >> n;

	//dp init
	for (int i = 0; i < MAX; i++)
	{
		for (int j = i; j < MAX; j++)
		{
			if (i == 0) // 첫번째 다리의 경우
				dp[i][j] = j + 1;
			else if (i == j) // 같은 번호의 다리의 경우
				dp[i][j] = 1;
			else // 그 외의 경우
				dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
		}
	}

	for (int i = 0; i < n; i++)
	{
		int left, right;
		cin >> left >> right;

		cout << dp[left-1][right-1] << '\n';
	}

	return 0;
}