[BOJ] 1010

다리 놓기

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

분류

• Silver 5

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

해법

왼쪽 지역에서 위의 사이트는 아랫 사이트보다 오른쪽 지역의 위 사이트로만 가야 합니다.
순서가 정해져 있으므로 조합과 같습니다.

정답 코드

#include <iostream>
using namespace std;

// it calculate M combination N
// M * (M - 1) * ... * (M - N + 1) / (N)!
long long combination(int N, int M)
{
    long long numerator = 1;
    long long denominator = 1;

    if (N > (M / 2)) N = M - N; // m combination n == m combination m-n
    // cal numerator loop
    for (int i = M; i >= M - N + 1; i--) // M * (M - 1) * ... * (M - N + 1)
        numerator *= i;
    // cal denominator loop
    for (int i = 1; i <= N; i++) // N!
        denominator *= i;

    return numerator / denominator;
}

int main(void)
{
    int T;
    scanf(" %d", &T);
    for (int i = 0; i < T; i++)
    {
        int N, M;
        scanf(" %d %d", &N, &M);
        printf("%lld\n", combination(N, M));
    }
    return 0;
}