[백준] 2407 - 조합

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

2407번: 조합

얼핏 보면 간단한 조합 구현 문제이지만 범위를 봐야합니다. 최대값인 100_C_50 는 long long int 의 범위를 거뜬히 넘어버려 계산식으로만 하면 틀립니다. 그렇기에 string으로 구현해 줍니다. 기본적으로 dp를 베이스로 nCm = n-1Cm-1 + n-1Cm 을 이용하여 재귀를 돌려줍니다. n = m or m = 0 일 때 1을 반환하고 이 전의 값이 있으면 그대로 반환해줍니다. 그리고 이 두 값을 더할 때 string의 첫째자리만 더해서 문자열로 추가하는 방식으로 정답을 string으로 반환합니다. 통계 개념 조금과 문자열을 숫자로 변환할 수 있냐는 문제입니다.

#include <iostream>
#include <algorithm>
#include <string>
#define MAX 101
using namespace std;
typedef long long ll;

string dp[MAX][MAX];
ll n, m;

string calc(string s1, string s2) {
    ll sum = 0;
    string s;

    while (s1.length() || s2.length() || sum) {
        if (s1.length()) {
            sum += s1.back() - '0';
            s1.pop_back();
        }
        if (s2.length()) {
            sum += s2.back() - '0';
            s2.pop_back();
        }

        s.push_back((sum % 10) + '0');
        sum /= 10;
    }

    reverse(s.begin(), s.end());
    return s;
}

string DP(ll a, ll b) {
    if (a == b || b == 0)
        return "1";
    if (dp[a][b].length())
        return dp[a][b];
    return dp[a][b] = calc(DP(a - 1, b - 1), DP(a - 1, b));
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    cout << DP(n, m) << "\n";

    return 0;
}