[BOJ] 1010번 다리 놓기 (C++)

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

1010번: 다리 놓기

 

#include <iostream>
using namespace std;

int main() {
	int t, n, m;
	cin >> t;
	
	int dp[31][31] = {0, };
	for(int i = 1; i <= 30; i++){
		for(int j = 1; j <= 30; j++){
			if(i == 1){
				dp[i][j] = j;
			}
			else if(i == j){
				dp[i][j] = 1;
			}
			else{
				for(int k = i - 1; k < j; k++){
					dp[i][j] += dp[i - 1][k];
				}
			}
		}
	}
	
	for(int i = 0; i < t; i++){
		cin >> n >> m;
		cout << dp[n][m] << endl;
	}
	return 0;
}

서쪽의 사이트 수가 1인 경우 경우의 수는 동쪽 사이트 수와 같다.   dp[i][j] = j

서쪽의 사이트 수와 동쪽의 사이트 수가 같은 경우, 경우의 수는 항상 1이다.  dp[i][j] = 1

 

규칙을 찾아보면 다음과 같다. (행은 서쪽 사이트 수, 열은 동쪽 사이트 수)

	1	2	3	4	5
1	1	2	3	4	5
2		1	1+2	1+2+3	1+2+3+4
3			1	1+(1+2)	1+(1+2)+(1+2+3)
4				1	1+1+(1+2)
5					1

따라서 서쪽의 사이트 수가 1인 경우, 서쪽의 사이트 수와 동쪽의 사이트 수가 같은 경우를 제외하면

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