[C/C++] BOJ 1010 :: 다리놓기

BOJ 1010 :: 다리놓기

문제 링크 : https://www.acmicpc.net/problem/1010

나의 풀이

다리 만들기는 아래와 같은 규칙이 있다.

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

이를 이용하여 모든 table을 채운 뒤, input에 따른 dp[N][M]을 출력한다.

사용되지 않는 0행을 이용해서 table을 채우기 위해 0행을 모두 1로 채워주었다.

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_1010/BOJ_1010.cpp

// 백준알고리즘 1010번 :: 다리 놓기
#include<iostream>
using namespace std;
 
int T, N, M;
long long dp[31][31];
 
int main(void)
{
    for (int n = 0; n <= 30; n++)
    {
        dp[0][n] = dp[n][n] = 1;
    }
 
    for (int n = 1; n < 30; n++)
    {
        for (int m = 1; m <= (30 - n); m++)
        {
            dp[m][m + n] = dp[m][m+n-1] + dp[m-1][m+n-1];
        }
    }
 
    cin >> T;
    while (T--)
    {
        cin >> N >> M;
        cout << dp[N][M] << '\n';
    }
 
    return 0;
}