[백준/c++] - 1010 다리 놓기

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

1010번: 다리 놓기

 

 

 

 

목차
1. 문제 풀이
2. 코드

 

 

 

 

 

문제풀이

 처음 문제를 보고선 고등학교 확통때 배운 조합(Combination)이 떠올랐다. 하지만 알고리즘 분류가 DP여서 dp로 풀어보는 쪽으로 접근하였다.

 

 

 

 

 

 dp로 풀기위한 핵심은 이전에 계산한 값들을 통해 다음 값들을 계산할 수 있는가를 판단하는 것이다. 이 문제의 경우 이 조건을 충족하기에 dp로 풀 수 있었다. 다음 예시를 보자.

 

 

 

 

 

 왼쪽에 2개의 사이트, 오른쪽에 3개의 사이트가 놓인 경우를 나타낸 그림이다. 여기서 우리는 이 상태를 memo[2][3]이라고 나타낸다고 약속하고 이 경우의 수를 이미 알고 있다고 가정해보자.

 

 

 

 

 

 

 

 

 

 

 오른쪽 가장 아래에 한개의 사이트가 새로 생겨났다고 해보자. 이 상태에서의 경우의 수는 memo[2][4]로 나타낸다. 여기서 잘 생각해보면 가장 아래에 새로 생겨는 사이트에는 왼쪽에서 가장 아래에 있는 사이트에서만 다리를 연결 할 수 있다. 한번 연결해보자.

 

 

 

 

 

 

 

 

 

 

 그렇다면 새로운 사이트에 왼쪽의 가장 아래 사이트에 연결하여 고정시킨 상태에서의 경우의 수를 어떻게 구할 수 있을까? 우린 처음의 상태를 memo[2][3]이라고 나타내었으니 왼쪽과 오른쪽에 사이트를 하나씩 제거한것과  동일하므로 이 상태에서의 경우의 수를 memo[1][3]이라고 나타낼 수 있을 것이다.

 

 

 

 

 또한 사이트가 생겨난 새로운 상태인 memo[2][4]는 이전의 경우의 수 memo[2][3]을 포함하며 위에서 말한 새로운 사이트를 무조건 사용하는 경우도 같이 포함한다.

 

 

 

 

 이 논리를 통해 새로운 상태 memo[2][4]를 이전에 계산한 값들을 통해 계산할 수 있다. memo[2][4]의 이전 값들을 나타내는 memo[1][1] ~ memo[2][3]의 값들을 모두 알고 있다고 가정하였으므로, memo[2][4] = memo[2][3] + memo[1][3]으로 나타낼 수 있다. 이를 바탕으로 점화식을 세우면 아래와 같이 나타낼 수 있다.

 

 

 

 

 

memo[i][j] = memo[i][j - 1] + memo[i - 1][j - 1]

 

 

 

 

 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// 다리를 놓을 수 있는 경우의 수
// dp 문제? -> 오른쪽에 사이트가 하나 늘어날 때 어떤 변화가 일어나는가?
// ex) 2 2 -> 2 3, 경우의 수 2증가(다리 한칸씩 내리기) 
// 새로운 사이트가 생긴다는 것 -> 가장 아래있는 왼쪽 사이트를 새로생긴 오른쪽 사이트에 고정 시킨다면
// 새로 추가되는 경우의 수는 이전 memo[i - 1][j - 1] 의 개수와 동일하다. 즉, i와 j를 통해 이전 계산 값들로 새로운 값을 계산할 수 있다.
// 
// memo[i][j] = memo[i][j - 1] + memo[i - 1][j - 1] -> 사이트를 추가하기 전의 값 + 사이트를 추가하고 나서의 값
// 
// 
// memo[i][j] -> 왼쪽 사이트가 i, 오른쪽 사이트가 j일때 다리를 놓을 수 있는 경우의 수


int T;
int memo[31][31];
void input() {
	cin >> T;
	for (int i = 0; i < T; i++) {
		int right, left;
		cin >> right >> left;
		cout << memo[right][left] << endl;
	}
}

void init() {
	// 기본값 세팅
	for (int i = 1; i < 31; i++) { // 1개일 때는 오른쪽 사이트의 개수만큼
		memo[1][i] = i;
	}

	for (int i = 2; i < 31; i++) {
		for (int j = 2; j < 31; j++) {
			memo[i][j] = memo[i][j - 1] + memo[i - 1][j - 1];
		}
	}
}


int main() {

	init();
	input();

	

	return 0;
}