조합 2407

문제

접근 방법

처음에는 unsigned long long으로 해결될 줄 알았다.
하지만 범위가 더 넓었고 그래서 오답이 떴다.
string을 활용하여 숫자 연산을 해야 한다.

코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string dp[101][101];

string addString(string num1, string num2)
{
    int sum = 0;
    string ret;
    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();
        }
        ret.push_back(sum % 10 + '0');
        sum /= 10;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

string comb(int n, int m)
{
    if (n == m || m == 0)
        return "1";

    if (!dp[n][m].empty())
        return dp[n][m];

    return dp[n][m] = addString(comb(n - 1, m - 1), comb(n - 1, m));
}

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

풀이

조합을 재귀적으로 푸는 방법과 큰 수에 대한 연산을 string으로 해결하는 방법으로 푸는 문제이다.
문자열로 숫자 연산을 처리하는 것은 자주 접하지 못하는 문제이기에 한 번쯤 풀어보는 것도 도움이 되는 것 같다.