백준 1010번 : 다리 놓기

문제 링크 : https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

 

 문제설명 

 

1. 서쪽 과 동쪽의 사이트 수가 주어지고 이때 서쪽과 동쪽을 잇는 다리를 건설할수 있는 경우의 수를 출력.

2. 사이트: 다리 짓기 적합한 장소 , 다리는 서로 겹쳐서 건설 불가.

 

 

 알고리즘 

 

1. 다리가 서로 겹처서 건설이 불가하고 N<= M 이므로 mCn 을 구하면 되는문제이다.

2. 이때 n,m<=30 이므로 조합의 수를 계산할때 mCn = mC(m-n) 을 활용 해야함.

 

 

 코드 

 

#include<iostream>
 
 
using namespace std;
 
long long func(int n, int m) {
    long long a=1, b=1;
    int num = m;
    for (int i = 2; i <= n; i++) {
        b *= i;
    }
    for (int i = 0; i < n; i++) {
        a = a * num;
        num--;
    }
    
    return a / b;
}
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int T, N, M;
 
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> N >> M;
        if (N * 2 < M) {
            cout << func(N, M);
        }
        else {
            cout << func(M - N, M);
        }
        cout << '\n';
    }
}