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

1010. 다리 놓기

1010번: 다리 놓기

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

내 한참 모자른 수학 실력을 알 수 있었던 문제...

 

분명 문제를 보자마자 어? 경우의 수! 어? 팩토리얼! 어? 순열! 까지는 나왔지만... 어? 조합이 안 나와버렸다...

분명히 순열 문제인데... 하면서 끙끙 앓다가...

 

일단 인터넷을 보지 않고 문제를 풀려고 했지만... 우매한 내 머리에 든 수학 실력으로는 도저히 풀지 못할 것 같아서

인터넷 대신 수학 선생님께 여쭤보았다.

 

선생님이 말씀하신 방법은 조합!

서쪽 다리에서 동쪽 다리를 순서 없이 모두 선택하는 방식이니까... 내가 생각했던 건 그냥 순열이지만...

 

nPr = n! / (n-r)!

조합은...

nCr = n! / ((n-r)!*r!)

 

그런데 여기서 문제가 생긴 게... 30 팩토리얼이 unsigned long long int에도 담아지지 않는다는 것... 나는 선생님께 팩토리얼을 덜 구할 수 있는 조합을 어떻게 구하는지 여쭤보았고...

 

순서대로 고르는 게 같다면, 순서대로 버리는 것도 같다는 답을 얻었다.

 

따라서 이렇게 되는 것.

nCr = nC(n-r)

그렇다면 서쪽 다리의 개수 > 동다개-서다개라면 위에 있는 식으로 치환해 계산해주면 되는 것!

 

그렇다면 최악의 경우가 나오더라도...

input => 30 30

30C30이지만...
30C0으로 계산하게 된다.

=> 1

 

코드!

#include<iostream>
using namespace std;

typedef unsigned long long int ulli;

ulli Fac(int n, int cnt)
{
    if (n <= 1 || cnt == 0) return 1;
    return n * Fac(n - 1, cnt - 1);
}

int main()
{
    int tCnt;
    cin >> tCnt;

    while (tCnt--)
    {
        int a, b;
        cin >> a >> b;

        if (b - a < a)
            a = b - a;

        cout << Fac(b, a) / Fac(a, a) << '\n';
    }
}

아직 별로 많은 문제를 풀어보진 않았지만... 난 특히 수학에 더 약한 것 같다.

 

이런 문제를 푸는 데는 고등과정만으로도 충분하니, 학교에서 배우는 수학을 시험용으로만 배우지 말고, 문제를 푸는데 써먹어봐야겠다...