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

문제링크 : https://boj.kr/1010

이 문제는 M개의 사이트에 N개의 다리를 놓는 가지수를 구하면 되는 문제로 조합을 이용하여 풀었다.

MCN = M! / ((M-N)! * N!) 을 구현하면 된다.

6C4를 구하는 경우 (6*5*4*3*2*1) / ( (2*1) * (4*3*2*1) ) 인데 (4*3*2*1)에 해당하는 N!이 약분되어 (6*5) / (2*1)인 것을 중학교때 많이 배웠을 것이다. (M-N)!과 N! 중에서 더 많은 숫자를 제거할 수 있는 값을 고르면 되고 이를 그대로 식으로 표현하면 된다.

// BOJ 1010 다리 놓기
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int tc;
    cin >> tc;
    while (tc--) {
        int n, m;
        long long result = 1;
        cin >> n >> m;
 
        // nCr을 위해 n-r과 r 중에 작은 값 선택
        n = n > m - n ? m - n : n;
        // nCr
        for (int i = 0; i < n; i++)
            result *= m - i; // n! / (n-r)! 또는 r!
        for (int i = 2; i <= n; i++)
            result /= i; // r! 또는 (n-r)!
        cout << result << '\n';
    }
 
    return 0;
}