[Algorithm]Baekjoon 1010번 : 다리 놓기

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

1010번: 다리 놓기

 

int t, n, m;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    vector<long long> answers;
    for (int i = 0; i < t; ++i)
    {
        cin >> n >> m;
 
        // m! / (m-n)! * n!     무조건 m이 n이상임.
        long long answer = 1;
        int temp = 1;
 
        for (int j = m; j > m - n; --j)
        {
            answer *= j;
            answer /= temp;
            ++temp;
        }
 
        answers.push_back(answer);
    }
 
    for (auto& temp : answers)
    {
        cout << temp << endl;
    }
}
 

조합으로 풀 수 있는 문제이다.

동쪽사이트가 항상 서쪽보다 많기 때문에, 동쪽사이트에서 서쪽사이트개수만큼 순서없이 뽑기만 하면된다.

왜냐하면 뽑은다음 위에서부터 차례대로 연결하면 되기 때문.

그렇다면 동쪽사이트 개수가 m개, 서쪽사이트개수가 n개라 했을 때 mCn이 된다.

 

그렇다면 공식은 m! / (m-n)! * n!이 되는데 m값은 최대 30이기 때문에 각각의 값들을 따로 구하려고하면 값이 너무 커져서 하나의 변수에 담기가 힘들다. (m값이 30이면 30!을 하나의 변수에 담아야하는데 unsigned long long으로 못담음)

그래서 위 코드처럼 곱하면서 동시에 나눠버리는 것이다.

 

왜 위 코드처럼 되는지는 직접 노트에다 몇번 끄적이면 감이온다.

일단 j를 m부터 m-n까지의 값이고 그걸 곱하는 이유는, 기본적으로 m!인것을 분모에서 n!으로 나눠버리기 때문이다.

거기에 더해서 (m-n)!으로도 나눠야하기 때문에 temp라는 값을 사용한 것이다.