[C++] 백준 다리놓기

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

1010번: 다리 놓기

풀이

왼쪽 사이트를 순서 있게 오른쪽 사이트와 연결하는 문제입니다.

 

순서 있는 경우의 수는 조합을 사용해 해결할 수 있습니다.

예를 들어, 3개(M)의 사이트 중 2개(N)의 사이트를 순서 있게 연결하는 방법은 3C2 = 3가지가 존재합니다.

 

이 때, nCr = n-1Cr-1 + n-1Cr 이므로 파스칼의 삼각형 형태를 사용해 해결할 수 있습니다.

가능한 조합을 모두 계산해 주고 M, N 에 맞도록 답을 출력해주면 해결됩니다.

 

리뷰

조합 문제를 다이나믹 프로그래밍을 사용해서 효율적으로 해결할 수 있음을 학습할 수 있습니다.

#include <iostream>

using namespace std;

int N, M, T;
long long answer;
int dp[31][31];

void combination()
{
    for (int i=0; i<31; i++) {
        dp[i][0] = 1;
        dp[i][i] = 1;
        for (int j = 1; j < i; j++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    // freopen("test.txt", "r", stdin);

    cin >> T;
    combination();
    for (int i=0; i<T; i++) {
        cin >> N >> M;
        cout << dp[M][N] << "\n";
    }   

    return 0;
}