백준 1010

백준 1010번 문제는 다리놓기 문제입니다. n개의 사이트와 m개의 사이트가 있을 때, n개의 사이트와 m개의 사이트를 다리로 연결하되, 다리가 겹치지 않도록 다리를 놓을 수 있는 경우의 수를 구하는 문제입니다. 즉, n개의 사이트 중에서 r개를 고르는 경우의 수인 조합론적인 문제입니다.
이 문제를 해결하기 위해서는 조합론의 개념을 이해하고, 동적 계획법(Dynamic Programming)을 이용해야 합니다. 조합론에서 n개 중 r개를 선택하는 경우의 수는 nCr = n! / (r! * (n-r)!)으로 계산할 수 있습니다. 그러나 이 방법은 매우 큰 수를 다루게 되면 계산이 불가능합니다.

따라서, 동적 계획법을 이용해 nCr을 구하는 방법을 사용합니다. 동적 계획법을 이용하면 시간 복잡도를 크게 줄일 수 있으며, 중복되는 계산을 피할 수 있습니다.
동적 계획법을 이용하여 nCr을 구하는 방법은 다음과 같습니다.
nC0 = 1
nCn = 1
nCr = (n-1)C(r-1) + (n-1)Cr
위 점화식을 이용하여 2차원 배열 dp를 이용하여 문제를 해결할 수 있습니다. dp[i][j]는 i개의 사이트와 j개의 사이트를 연결하는 경우의 수를 의미합니다. 따라서, dp[n][m]이 정답이 됩니다.

기저조건으로, dp[1][j]는 j개의 사이트 중에서 1개를 선택하는 경우의 수인 j가 됩니다. 그리고 dp[i][i]는 i개의 사이트 중에서 i개를 선택하는 경우의 수이므로 1이 됩니다.
그리고, dp[i][j]를 구하기 위해서는 dp[i-1][k]를 이용하여 계산할 수 있습니다. 따라서, k는 i-1에서 j-1까지 변하는 값을 가집니다. 이를 이용하여, dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j-1]으로 구할 수 있습니다.
위의 알고리즘을 이용하여 문제를 해결할 수 있습니다.

#include <iostream>
#include <cstring>
using namespace std;

int dp[31][31];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        memset(dp, 0, sizeof(dp)); // dp 배열 초기화
        for (int i = 0; i <= m; i++) {
            dp[1][i] = i;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = i; j <= m; j++) {
                for (int k = i - 1; k < j; k++) {
                    dp[i][j] += dp[i - 1][k];
                }
            }
        }
        cout << dp[n][m] << '\n';
    }
    return 0;
}