백준 #1010. 다리 놓기 (C++ Dynamic Programming)

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

1010번: 다리 놓기

 

N개의 서쪽 사이트에서 M개의 동쪽 사이트로 이어지는 다리의 개수를 구하는 문제.

조건 1) N은 M보다 작거나 같다.

조건 2) 다리는 서로 겹처질 수 없다.

 

N*M size의 이차원 배열을 만들고, 각각의 값을 적어보면 패턴이 한눈에 잘 보인다.

 

우선 쉽게 생각해보면, N과 M이 같을 때에는 경우의 수가 1이다.

 

 

N = M = 1인 경우

 

 

N = M = 3인 경우

 

 

만약 N보다 M이 1 클 때에는, 즉, N + 1 == M일 때는 경우의 수가 M이다.

 

N = 2, M = 3인 경우

이런 식으로 말이다.

 

이렇게 하나씩 경우의 수를 구해보면,

 

bridge[n][m] = bridge[n][m-1] + bridge[n-1][m-1]

 

이라는 패턴을 찾을 수 있다.

즉, 이전 경우(n, m-1)보다 도착점이 하나 더 늘었다면, 그만큼 늘어난 경우의 수를 더해준다.

 

 

 

다음은 소스코드이다.

 

#include <iostream>
#include <vector>
using namespace std;

int main() {

	int testcase, bridge[31][31];
	vector<int> result;

	for (int i = 1; i <= 30; i++) { //initialization
		for (int j = i; j <= 30; j++) {

			if (i == 1) bridge[i][j] = j;
			else if (i == j) bridge[i][j] = 1;
			else bridge[i][j] = 0;
		}
	}

	cin >> testcase;

	for (int i = 0; i < testcase; i++) {

		int west, east;
		cin >> west >> east;

		if (bridge[west][east] > 0) result.push_back(bridge[west][east]);
		else {

			for (int p = 2; p <= west; p++) { //dynamic programming
				for (int q = p + 1; q <= east; q++) {
					if (bridge[p][q] == 0) bridge[p][q] = bridge[p][q - 1] + bridge[p - 1][q - 1];
				}
			}

			result.push_back(bridge[west][east]);
		}
	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << '\n';
	}
	return 0;
}