[백준] 2407 조합

2407번: 조합

 

www.acmicpc.net

풀이

조합을 구현하는 문제이다. nCm = n-1Cm + n-1Cm-1 이라는 규칙이 있기 때문에 동적계획법으로 쉽게 구현할 수 있다. 하지만 이 문제는 long long 범위를 벗어나기 때문에 string으로 정수를 구현하여 해결하였다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

string dp[101][101];

string addTwoNumber(string num1, string num2) {
    long long sum = 0;
    string result;

    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();
        }

        result.push_back((sum % 10) + '0');
        sum /= 10;
    }
    // 뒤에서부터 숫자를 더했으므로 뒤집어준다
    reverse(result.begin(), result.end());
    return result;
}

string comb(int n, int m) {
    string& ret = dp[n][m];
    if (ret != "") return ret;
    if (m == 0 || m == n) return ret = "1";
    return ret = addTwoNumber(comb(n - 1, m - 1), comb(n - 1, m));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    cout << comb(n, m) << '\n';
    return 0;
}