알고리즘) 백준 Baekjoon 1010번 다리놓기 풀이(dynamic programming)

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

이 문제는 다이나믹 프로그래밍으로 분류 되어있으나, 조합으로도 풀 수 있는 문제입니다.

(해보지 않아서 조합이 시간초과가 나는지는... 풀어서 다음에 올리겠습니다.)

우선 다이나믹 프로그래밍을 풀기 위해선 점화식을 세워야 합니다.
이 문제의 점화식은 dp[N][M] = dp[N-1][M-1] + dp[N-1][M-2] + ... + dp[N-1][N-1] 입니다.

우선 N=1, M=3 의 경우의 수는 3입니다.

N=2, M=4 일때는 다음과 같습니다.

1. 위 그림과 같이 첫번째 다리가 놓이게 되고 두번째 다리가 놓일 수 있는 수는 3입니다.

다리는 교차되어 놓아질 수 없기 때문에 다음은 아래 같이 표현합니다.

2. 위 그림의 경우 2가지 경우의 수가 있습니다.

3. 마지막으로 1가지의 경우의 수가 있습니다.

N=2, M=4일 때의 경우의 수는 3+2+1 로 총 6가지입니다.

그림을 자세히 보시면 첫번째 다리를 연결 한 후 남은 다리의 그림은 N=1, M=3일 때 경우와 동일 하며 2번의 경우 N=1, M=2 때, 3번은 N=1, M=1일 경우와 똑같습니다. 

N=2 일때 N=1일 때의 결과를 활용한 것을 볼수 있습니다.

이런 방식으로 N=3, M=5일 때는 dp[2][4]+dp[2][3]+dp[2][2] 로 10의 결과를 얻을 수 있습니다.

그렇기 때문에 점화식을 이용해 코드로 표현하면 다음과 같습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

int main() {     for (int i = 0; i < 31; i++)     {         for (int j = 0; j < 31; j++) {             cache[i][j] = 0;         }     }       for (int i = 0; i < 31; i++)     {         cache[1][i] = i;     }       for (int i = 2; i < 31; i++)     {         for (int k = i; k < 31; k++)         {             for (int l = k-1; l >= i-1; l--) {                 cache[i][k] += cache[i - 1][l];             }         }     }       cin >> T;     for (int i = 0; i < T; i++)     {         cin >> N >> M;           cout << cache[N][M] << endl;     } } Colored by Color Scripter

cs

저는 전처리 후 N,M에 해당하는 cache만 찍어주었습니다.

N, M값만큼 계산 후 답을 출력해도 무방합니다.