백준 1010 : 다리놓기(C++)

문제

풀이

처음에 조합(Combination)을 이용한 재귀로 풀면 되겠다는 생각을 했습니다.
하지만, 시간 제한으로 다른 방법을 찾아야했습니다.

Dynamic Programming을 이용해서 풀어보겠습니다.
dp[N][M]을 N개와 M개의 사이트로 만들 수 있는 다리의 수라고 정의하겠습니다.

조합은 파스칼 삼각형에서 nCr = n-1Cr-1 + n-1Cr입니다.
이식을 이용해서 dp의 점화식을 구하면 n은 M으로 r은 N으로 바꾸면 됩니다.
따라서 dp[N][M]= dp[N-1][M-1] + dp[N][M-1]입니다(dp[N][M] = nCr)

코드

#include <iostream>
using namespace std;

int main() {
    int T,N,M;
    int dp[31][31];

    for(int i = 0; i < 31; i++) {
        for(int j = 1; j < 31; j++) {
            // 파스칼 삼각형 오른쪽 변 값 1로 초기화
            if(i == j) {
                dp[i][j] = 1;
            }
            // 파스칼 삼각형 왼쪽 변 값 1로 초기화
            else if(i == 0) {
                dp[i][j] = 1;
            }
            else {
                dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
            }
        }
    }
    scanf("%d", &T);

    while(T--) {
        scanf("%d %d", &N, &M);
        printf("%d\n", dp[N][M]);
    }
    return 0;
}