[백준][C++] 1010: 다리 놓기

문제

1010번: 다리 놓기

풀이

수학, 다이나믹 프로그래밍, 조합론

 

다리는 서로 겹쳐질 수 없으므로, 동쪽의 사이트 M개 중에서 N개의 사이트를 선택하는 경우의 수이다. 

int Combination(int n, int r)
{
    if (n == r || r == 0)
    {
        return 1;
    }
    else
    {
        return Combination(n - 1, r - 1) + Combination(n - 1, r);
    }
}

단순히 위의 함수로만 구하면 시간 초과가 발생한다. 다이나믹 프로그래밍을 섞어 이전에 구했던 조합의 결과를 활용하면 시간 초과가 발생하지 않는다. 

코드

#include <iostream>
#include <memory.h>

using namespace std;

// 캐시를 두어 시간초과 방지
int cache[30][30];

int Combination(int n, int r)
{
    if (n == r || r == 0)
    {
        cache[n][r] = 1;
        return 1;
    }
    else if (cache[n][r] != -1)
    {
        return cache[n][r];
    }
    else
    {
        cache[n][r] = Combination(n - 1, r - 1) + Combination(n - 1, r);
        return cache[n][r];
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;

    memset(cache, -1, sizeof(cache));

    while (T--)
    {
        // 동쪽의 사이트 중에서 N개를 고르는 경우의 수
        int N, M;
        cin >> N >> M;

        cout << Combination(M, N) << '\n';
    }

    return 0;
}