[C++] 백준 2407 조합

#include <iostream>
 
std::string DP[101][101] = {};
 
std::string Add(std::string sFirstNumber, std::string sSecondNumber)
{
    std::string sNumber = "";
    int iSum = 0;
    int iSize = std::max(sFirstNumber.size(), sSecondNumber.size());
 
    for (int i = 0; i < iSize || iSum; ++i)
    {
        if (sFirstNumber.size() > i)
            iSum += sFirstNumber[i] - '0';
 
        if (sSecondNumber.size() > i) 
            iSum += sSecondNumber[i] - '0';
 
        sNumber += iSum % 10 + '0';
        iSum /= 10;
    }
 
    return sNumber;
}
 
std::string combi(int iN, int iM) 
{
    if (iN == iM || iM == 0)
        return "1";
 
    std::string& ans = DP[iN][iM];
 
    if (ans != "") 
        return ans;
 
    ans = Add(combi(iN - 1, iM - 1), combi(iN - 1, iM));
 
    return ans;
}
 
int main() 
{
    int N = 0;
    int M = 0;
 
    std::cin >> N >> M;
 
    combi(N, M);
 
    for (int i = DP[N][M].size() - 1; i >= 0; --i)
    {
        std::cout << DP[N][M][i];
    }
 
    return 0;
}

1. nCm은 n-1Cm + n-1Cm-1 를 아는 것이 제일 중요합니다. 재귀함수로 불러서 계산해야 합니다. (DP)

2. long long의 범위를 넘어가기 때문에 바로 계산할 수가 없습니다. 그렇기 때문에 string으로 계산해야합니다.