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

문제설명

---

입출력 예제

---

개념

　경우의 수를 계산하는 문제다. 이때 순서에 상관없이 N개의 다리와 M개의 다리를 이으면 되므로, 조합의 개념을 이용하면 쉽게 해결할 수 있다.

---

풀이

#include <iostream>
#include <cmath>

int main()
{
    int T, N, M;
    std::cin >> T;

    while (T--)
    {
        std::cin >> N >> M;
        std::cout << combination(M, N) << '\n';
    }
}

　테스트 케이스의 개수 T, 다리의 개수 N, M을 초기화하고, 각 경우의 mCn의 값을 출력한다.

 

long long int combination(int& n, int& m)
{
    if (n == m)
        return 1;

    if (m == 1)
        return n;

    long double result = 1;
    int j = 0;

    for (int i = n; i > 0; --i)
    {
        int d1 = m <= 0 ? 1 : m;
        int d2 = (n - m - j) <= 0 ? 1 : (n - m - j);
        int d = d1 * d2;

        if (d <= 0)
            d = 1;

        result *= i;
        result /= d;
        n--; m--; j++;
    }

    return std::round(result);
}

　조합의 경우 숫자가 크게 나올 수 있기 때문에 반환형을 long long int 타입으로 지정해야 한다. 조합의 공식에 따라 다음 경우를 먼저 처리한다.

• nCn = 1
• nC1 = n

　조합 공식은 다음과 같다.

 

 

　팩토리얼은 숫자가 너무 큰 경우가 많아 오버플로가 발생하기 십상이다 .따라서 분자와 분모를 따로 계산하고, result에 곱하거나 나누는 식으로 수의 범위를 줄여서 계산하였다. 예를 들어, 10C2의 경우에는 다음과 같은 과정으로 계산된다.

 

 

총합본

#include <iostream>
#include <cmath>

long long int combination(int& n, int& m)
{
    if (n == m)
        return 1;

    if (m == 1)
        return n;

    long double result = 1;
    int j = 0;

    for (int i = n; i > 0; --i)
    {
        int d1 = m <= 0 ? 1 : m;
        int d2 = (n - m - j) <= 0 ? 1 : (n - m - j);
        int d = d1 * d2;

        if (d <= 0)
            d = 1;

        result *= i;
        result /= d;
        n--; m--; j++;
    }

    return std::round(result);
}


int main()
{
    int T, N, M;
    std::cin >> T;

    while (T--)
    {
        std::cin >> N >> M;
        std::cout << combination(M, N) << '\n';
    }
}

---

풀이(2) 

　이러한 과정을 더욱 최적화하여 다음과 같이 풀었다.

 

#include <iostream>
using namespace std;

int main() 
{
    ios_base::sync_with_stdio(false);   cin.tie(nullptr);

    int T, N, M, tmp, result;

    cin >> T;

    while (T--) 
    {
        result = 1;
        tmp = 1;
        cin >> M >> N;

        for (int i = N; i > N - M; --i) 
        {
            result *= i;
            result /= tmp++;
        }

        cout << result << "\n";
    }
}