백준 1010번 다리 놓기

< 백준 1010번 다리 놓기 - 마포 코딩박 >

사용한 알고리즘: DP


 강의 서쪽에 N개, 동쪽에 M개의 사이트가 있을 때, N개의 다리를 놓을 수 있는 경우의 수를 구하는 문제입니다.

문제풀이는 다음과 같습니다.

(1) (코드 5~6)
 'dp[a][b] = 서쪽 a개, 동쪽 b개 일때 a개의 다리를 놓을 수 있는 경우의 수' 로 설정했습니다.

(2) (코드 9~10)
 초기값 dp[1][i] = i 입니다. 즉 서쪽 1개, 동쪽 i 개 일때, 1개의 다리를 놓는 경우는 i가지 입니다.

(3) (코드 11~20)
 동쪽 i개, 서쪽 j개 인 경우수는 (i-1)(j-1), (i-1)(j-2), ... (i-1)(j-1) 의 각 경우에다 위에 다리 하나 더 놓는경우라고 생각할 수 있습니다.
 즉 dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][i-1] 입니다.
 ( dp[i][j] 에서 i>j 인 경우수는 0 입니다. )
 예를들어 dp[3][5] = dp[2][4] + dp[2][3] + dp[2][2] 입니다.
 이를 통해 dp값을 계산합니다.

	#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;
	}

view raw BOJ 1010.cpp hosted with ❤ by GitHub