[실3] 2407 - 조합

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

#define MAX 101

int n, m;
string Cache[MAX][MAX];

string BigNumAdd(string num1, string num2)
{
    string res;
    long long sum = 0;

    while (!num1.empty() ||
           !num2.empty() ||
            sum)
    {
        if (!num1.empty())
        {
            sum += num1.back() - '0';
            num1.pop_back();
        }
        if (!num2.empty())
        {
            sum += num2.back() - '0';
            num2.pop_back();
        }
        res.push_back((sum % 10) + '0');
        sum /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

string Combination(int n, int r)
{
    if (n == r ||
        r == 0)
        return "1";

    string& res = Cache[n][r];

    if (res != "")
        return res;

    // 파스칼 삼각형
    return res = BigNumAdd(Combination(n - 1, r - 1), Combination(n - 1, r));
}

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    cout << Combination(n, m);
    return 0;
}