[C++] BOJ 1010 다리 놓기

문제

백준 1010번 다리놓기

www.acmicpc.net/problem/1010

1010번: 다리 놓기

코드

#include<iostream>
using namespace std;

int dp[35][35];
int n, m, t;

int main(void){
    for (int i = 0; i <= 30; i++){
        dp[0][i] = dp[i][i] = 1;
    }

    for (int i = 1; i < 30; i++){
        for (int j = 1; j <= (30 - i); j++){
            dp[j][j + i] = dp[j][j + i - 1] + dp[j - 1][j + i - 1];
        }
    }

    cin >> t;
    while (t--){
        cin >> n >> m;
        cout << dp[n][m] << '\n';
    }
}

풀이방법

각 경우의 수는 nCm과 같다. DP를 이용해 각 경우의 수를 모두 구해줬다.

고민과정

문제를 보자마자 조합계산법밖에 떠오르지 않았다. dp로 풀어야한다고 생각하다보니 조합의 규칙성이 뒤늦게 떠올랐다. 

너무 오랜만에 풀었더니 출력할 때 줄을 바꿔야하는걸 잊어버려서 계속 틀렸다..