[백준] 다리 놓기 (C++)

 

문제 URL:

www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

다음 문제는 각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력하는 프로그램으로

조합을 이용하여 풀면 되는 문제이다. 

 

주의할 점! a와 b에는 곱한 수들이 들어가기 때문에 int범위를 넘을 수 있으므로

데이터 타입을 long long int형으로 설정해주어야 한다.

---

#include<iostream>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n, m;
        long long a=1, b=1;
        cin >> n >> m;

        if(n==m)	//두 수가 같을 때 경우는 1가지
            cout << 1 << "\n";
        else
        {
            if(n>m/2)	//mCn = mC(m-n)
                n = m-n;

            for(int i=0; i<n; i++)
            {
                a *= m;	//분자
                m--;
            }
            for(n; n>1; n--)
                b *= n;	//분모

            cout << a/b << "\n";
        }
    }
}