2407 조합

2407 조합 (c++)

문제

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

접근 방식

조합, 파스칼의 삼각형, 동적 계획법

처음엔 _nC_r = _nP_r / r! 로 풀어보려고 했다.
하지만 ₁₀₀C₅₀까지 가면 자릿수가 unsigned long long으로고 커버할 수 없이 커져버린다.
그래서 큰 수를 커버하려고 string 연산으로 수를 표현하려고 했다.
하지만 곱하기는 어떻게든 큰 수로 표현을 하겠는데, 큰수의 나누기 연산을 구현하기가 너무 까다로웠다. (사실 귀찮았다)
아무리 생각해도 이건 이렇게 푸는 문제가 아닌 것 같아서 1시간 고민한 끝에 다른 사람의 접근법을 봤다.
조합 = 파스칼의 삼각형 이라는 공식이 적용됐다.

_nC_r = _n-1C_r-1 + _n-1C_r

이러면 조합을 곱셈 나눗셈이 아닌 단순히 큰 수의 덧셈만으로 구할 수 있었다. 또 재귀적이었기 때문에 dp를 사용하기 편했다.

문제 풀이

#include <iostream>
#include <string>
using namespace std;
int N, M;
string arr[101][101] = {};
string AddBigNum(string a, string b)
{
    if (b.length() > a.length())
    {
        string temp = a;
        a = b;
        b = temp;
    }

    int nextNum = 0;
    for (int i = 0; i < b.length(); ++i)
    {
        int num = b[i] - '0' + a[i] - '0' + nextNum;
        if (num >= 10)
        {
            nextNum = num / 10;
            num %= 10;
        }
        else nextNum = 0;

        a[i] = num + '0';
    }

    if (nextNum)
    {
        if (a.length() == b.length()) a += nextNum + '0';
        else
        {
            for (int i = b.length(); i < a.length(); ++i)
            {
                int num = a[i] - '0' + nextNum;
                if (num >= 10)
                {
                    nextNum = num / 10;
                    num %= 10;
                }
                else nextNum = 0;

                a[i] = num + '0';
                if (nextNum == 0) break;
            }
            if (nextNum) a += nextNum + '0';
        }
    }
        
    return a;
}

string Comb(int n, int r)
{
    if (arr[n][r] == "")
    {
        if (r == 0 || r == n) arr[n][r] = "1";
        else arr[n][r] = AddBigNum(Comb(n - 1, r - 1), Comb(n - 1, r));
    }
    return arr[n][r];
}

int main()
{
    cin >> N >> M;
    Comb(N, M);
    for (int i = arr[N][M].size() - 1; i >= 0; --i)
    {
        cout << arr[N][M][i];
    }
    cout << endl;
    return 0;
}

다시 생각해 볼 점

1. _nC_r 은 _nP_r / r! 이기도 하지만 _nC_r = _n-1C_r-1 + _n-1C_r 이기도 하다. (파스칼의 삼각형이 훨씬 간결하고 동적 계획법을 사용하여 효율성도 높다.)
2. 앞으로 조합이 나온다면 무조건 파스칼의 삼각형을 대입해볼 생각을 해야겠다.