[BOJ] 1010번. 다리 놓기

문제 링크 : https://www.acmicpc.net/problem/1010

문제는 링크 참고.

풀이.

N = 서쪽의 사이트 갯수, M = 동쪽의 사이트 갯수

N = 2, M = 4일 때를 가정해보자

N(1)번 사이트와 M(1)번 사이트를 연결하면 남는 사이트들은 서쪽 사이트 1개 동쪽 사이트 3개가 남는다.

즉, N(1)번과 M(1)번을 연결하면 N = 1, M = 3 일 때의 가짓수가 나온다는 것이다.

그렇다면 마찬가지로 N(1)번과 M(2)번 사이트를 연결하면 남는 사이트들은 서쪽 사이트 1개 동쪽 사이트 2개가 남는다.

이것 또한 N(1)번과 M(2)번 사이트를 연결하면 N = 1, M = 2개의 가짓수가 나온다는 것이다.

이렇게 각 사이트마다 연결하여 가짓수를 구하면

(N = 1, M = 3 가짓수) + (N = 1, M = 2 가짓수) + (N = 1, M = 1 가짓수) = (N = 2, M = 4 가짓수)

이라는 식이 완석된다.

자 그렇다면 N = 2, M = 3일 때를 가정해보자

위에서 했던 것과 마찬가지로 식을 구하면

(N = 1, M = 2 가짓수) + (N = 1, M = 1 가짓수) = (N = 2, M = 3 가짓수) 가 된다.

자 여기까지 구하면, 위의 첫번째 식(N = 2, M = 4 가짓수)을 두번째 식(N = 2, M = 3 가짓수)를 통해 줄일 수 있게된다.

(N = 1, M = 3 가짓수) + { (N = 1, M = 2 가짓수) + (N = 1, M = 1 가짓수) } = (N = 2, M = 4 가짓수)

위 식에서 중괄호("{ }")로 묶은 값은 (N = 2, M = 3 가짓수)와 같은 값이므로 다음과 같이 식을 바꿀 수 있다.

(N = 1, M = 3 가짓수) + { (N = 2, M = 3 가짓수) } = (N = 2, M = 4 가짓수)

그러므로 점화식은

D[i][j] : 서쪽 사이트 i개와 동쪽 사이트 j개로 다리를 교차하지 않고 이을 수 있는 경우의 수

D[i][j] = D[i - 1][j - 1] + D[i][j - 1];

이된다.

#include <stdio.h>
 
int main() {
    int D[31][31] = {0};
    int T = 0, N = 0, M = 0;
    int save_idx_i = 2; 
    
    for (int i = 1; i <= 30 ; i ++)
        D[1][i] = i; // 서쪽 사이트가 1개일 때의 경우는 미리 채워둠. 
    
    scanf("%d", &T);
    
    while (T--) {
        scanf("%d %d", &N, &M);
        
        for (int i = save_idx_i ; i <= N ; i ++)
            for (int j = i ; j <= M ; j ++)
                D[i][j] = D[i - 1][j - 1] + D[i][j - 1];
                
        printf("%d\n", D[N][M]);
    }
    
    return 0;
}