(1010)(DP) 백준 다리놓기

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

풀이

---

i개의 서쪽 사이트와 j개의 동쪽 사이트를 잇는 다리를 지을 수 있는 경우의 수 dp[i][j]라고 하자.

dp[1][1]

dp[1][2]    dp[2][2]

dp[1][3]    dp[2][3]    dp[3][3]

dp[1][4]    dp[2][4]    dp[3][4]    dp[4][4]

.

.

.

이런식으로 dp[N][M]까지의 dp를 모두 구할 것이다.

이해하기 쉽게 예를 들어보기로 한다.

ex) 사이트에 번호를 메기고 dp[2][4]의 다리를 놓는 경우의 수를 알고싶다. 

1과 2의 경우로 나누어 생각해보자 

1번의 경우

---

먼저 그림의 1번 경우와 같이 2-4를 잇게 되면 N-1 개의 사이트와 M-1개의 사이트를 잇는 경우의 수를 구하는 꼴이 된다.

 즉, dp[1][3]의 값이라고 할 수 있다.

2번의 경우

---

다음은 그림의 2번 경우와 같이 2-3을 잇게되면 N개의 사이트와 M-1개의 사이트를 잇는 경우의 수를 구하는 꼴이 된다.

즉, dp[2][3]의 값이라고 할 수 있다.

dp[N][M] = dp[N-1][M-1] + dp[N][M-1];

위처럼 모든 dp에 성립하는 식이 만들어지게 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
 
int main() {
    int dp[31][31] = { 0 };
    int n, N, M;
 
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++) {
        scanf("%d %d\n", &N, &M);
    
            for (int i = 1; i <= M; i++) {
                dp[1][i] = i;
                for (int j = 2; j <= i; j++) {
                    dp[j][i] = dp[j - 1][i - 1] + dp[j][i - 1];
                
                }
            }
        printf("%d\n", dp[N][M]);
    }
 
    return 0;
 
}