백준 문제풀이

BOJ 1010.cpp

#include <iostream>
using namespace std;

int N, a, b;
// dp[a][b] : 서쪽 a개, 동쪽 b개 일때 가능한 다리 경우의 수
int dp[33][33];

int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	// 초기값 설정
	for (int i = 0; i < 30; ++i) dp[1][i] = i;
	// dp값 계산
	for (int i = 2; i < 30; ++i){
		// dp[i][j] 에서 i>j 인 경우의 수는 0 이다.
		for (int j = i; j <= 30; ++j){
			// 예를들어 dp[3][5] = dp[2][4] + dp[2][3] + dp[2][2] 이다. 
			for (int k = j; k >= i; --k){
				dp[i][j] += dp[i-1][k-1];
			}
		}
	}
	cin >> N;
	for (int i = 0; i < N; ++i){
		cin >> a >> b;
		cout << dp[a][b] << '\n';
	}
	return 0;
}