[BOJ 2407] 조합 (C++)

조합(Silver 2)

문제

전체 문제 보기

2407번: 조합

접근법

이 문제는 조합에 대한 이해를 바탕으로 점화식을 세워야 하며, 큰 수 덧셈을 구현할 수 있어야 합니다. 조합은 \(_{n}\mathrm{C}_{r} = _{n-1}\mathrm{C}_{r} + _{n-1}\mathrm{C}_{r-1} \)라는 성질이 있습니다. 이를 DP의 탑 다운 방식을 활용하여 구현할 수 있습니다. 그리고 계산 과정에서 나오는 수가 64bit 정수 크기를 넘기 때문에 문자열을 활용하여 큰 수 덧셈을 별도로 구현해야 합니다.

전체 구현

#include <iostream>
#include <string>
#include <array>
#include <algorithm>

#define endl '\n'
using namespace std;

array<array<string, 101>, 101> cache{};

string BigIntAdd(const string& lhs, const string& rhs)
{
    string retval;
    unsigned int lidx{lhs.size()}, ridx{rhs.size()};

    int sum{};
    // 1의 자리수 부터 덧셈 진행
    while (lidx > 0 || ridx > 0 || sum > 0)
    {
        if (lidx > 0)
        {
            sum += lhs[--lidx] - '0';
        }

        if (ridx > 0)
        {
            sum += rhs[--ridx] - '0';
        }
        retval.push_back((sum % 10) + '0');
        sum /= 10;
    }
    // 역순으로 저장되었기 때문에 문자열을 뒤집는다.
    reverse(retval.begin(), retval.end());

    return retval;
}

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

    //cout << n << " " << r << endl;
    if (cache[n][r] != "")
        return cache[n][r];

    cache[n][r] = BigIntAdd(comb(n - 1, r), comb(n - 1, r - 1));
    return cache[n][r];
}

int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int n, m; // 5 ≤ n ≤ 100 / 5 ≤ m ≤ 100 / m ≤ n
    cin >> n >> m;

    cout << comb(n, m) << endl;

    return 0;
}