BOJ 1010번 다리 놓기

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

1010번: 다리 놓기

 

왼쪽과 오른쪽에 다리가 있을 수 있는 경우를 몆가지 작은수로 직접 구해보자

그럼 2차원배열에 대한 dp점화식을 발견할 수 있게 된다

 

#include <cstdio>
#pragma warning(disable:4996)
int dp[30][30];
int N, M;
int main() {
 
    dp[1][1] = 1;
    for (int i = 1; i < 30; i++) dp[1][i] = i;
    for (int i = 2; i < 30; i++) {
        for (int k = 1; k < 30; k++) {
            if (i > k)dp[i][k] = 0;
            else dp[i][k] = dp[i - 1][k - 1] + dp[i][k - 1];
        }
    }
 
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &M);
        printf("%d\n", dp[N][M]);
    }
    
    
    return 0;
}