BOJ 1010번 : 다리 놓기

손풀기 문제로 풀었다.

기본적인 dp문제였고, 경우의 수를 물어보았으니, dp안에 들어가는 원소는 경우의 수가 될것 이라고 예상하고 풀면 되는 문제였다.

또한, 표를 한번 그려보면 어렵지 않게 규칙을 찾을 수 있다.

 

<Solution>

N과 M에 대해 표를 그려보면 아래와 같다.

위와 위의 왼쪽 원소의 합이 자신의 값이 되는것을 알 수 있다. 즉, 아래의 점화식 표현이 가능하다.

 

dp[m][n] = dp[m-1][n-1] + dp[m-1][n]

 

<소스코드>

#include<iostream>
using namespace std;
 
void Solve() {
    int t, n, m;
    cin >> t;
    for (int x = 0; x < t; x++) {
        int dp[31][31] = { 0, };
        cin >> n >> m;
        for (int i = 1; i <= m; i++) {
            dp[i][1] = i; //초기값
            for (int j = 2; j <= n; j++) 
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
        cout << dp[m][n] << endl;
    }
}
 
int main() {
    Solve();
}

<문제>

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

1010번: 다리 놓기