[백준 1010] 다리 놓기

이번 문제는 점화식만 구하면 된다.

DP[2][2] = DP[1][1]

DP[2][3] = DP[1][2] + DP[1][1]

DP[2][4] = DP[1][3] + DP[1][2] + DP[1][1]

 

규칙이 보이는가?

DP[2][3] = DP[1][2] + DP[1][1] 에서 DP[1][1]을 DP[2][2]로 치환하면

DP[2][3] = DP[2][2] + DP[1][2]

 

DP[2][4] = DP[1][3] + DP[1][2] + DP[1][1] 에서 DP[1][2] + DP[1][1]를 DP[2][3]으로 치환하면

DP[2][4] = DP[2][3] + DP[1][3]

 

 

그림으로 그리면 쉽다. 이해하기. 한번 해보는 걸 추천s

 

<소스코드>

#include <iostream>

using namespace std;

int main()
{
    int T;
    int DP[31][31] = { 0 };

    cin >> T;
    while(T--){
        int N, M;
        cin >> N >> M;

        for(int i = 1; i <= M; i++){
            DP[1][i] = i;
        }

        for(int i = 2; i <= N; i++){
            for(int j = 2; j <= M; j++){
                DP[i][j] = DP[i-1][j-1] + DP[i][j-1];
            }
        }

        cout << DP[N][M] << endl;
    }

    return 0;
}

점화식만 찾으면 쉽다.

끝.