[BOJ] 1010 다리놓기

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

Note

만들 수 있는 다리의 총 합을 구하는 문제
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;
}

2019-01-12 13:30:00에 Tistory에서 작성되었습니다.