[백준] 2407.cpp : 조합

www.acmicpc.net/problem/2407

2407번: 조합

---

• unsigned long long 으로도 표현할 수 없는 크기의 범위이다.
• 큰 수에 대한 연산을 표현하는 자료 구조가 필요한데, 문자열 혹은 unsigned long long 의 배열 등이 있겠다.
• 문자열을 사용하게 될 경우, 숫자로 나타내지는 문자열 끼리의 합을 구해주는 15353 번 문제에서 조합을 구하는 공식만 적용한다면 금방 풀 수 있는 문제이다.
• 조합을 재귀적으로 구하는 경우에 시간 초과가 나지 않게 메모이제이션을 활용한다.

---

#include <iostream>

using namespace std;

int n, m;
string answers[101][101];                               // 메모이제이션

string plused(string a, string b)                       // 두 수의 합을 더해주는 함수 (15353번 소스코드)
{
    string temp = "";
    int digitUp = 0;
    while(a.size() != b.size())
    {
        if(a.size() < b.size())
        {
            a = '0' + a;
        }
        else
            b = '0' + b;
    }
    for(int i = a.size() - 1, k ; i >= 0 ; i--)
    {
        k = (a[i] - '0') + (b[i] - '0') + digitUp;
        if(k >= 10)
        {
            digitUp = 1;
            k -= 10;
        }
        else
        {
            digitUp = 0;
        }
        temp = char(k + '0') + temp;
    }
    if(digitUp == 1) temp = '1' + temp;
    return temp;
}

string check(int r, int k)                                                  // 재귀적으로 해당 조합의 값을 구하는 함수
{
    if(answers[r][k] != "") return answers[r][k];                           // 이미 구해놨던 값이 있으면 해당 값을 반환
    if(k == 0 || r == k)                                                    // 재귀 탈출 부분, nCr 에서 r 이 0 이거나 n과 r 이 같을 경우
    {
        answers[r][k] = "1";
        return "1";
    }
    else
    {
        answers[r][k] = plused(check(r - 1, k - 1), check(r - 1, k));       // 그게 아니라면, (n-1 C r-1) + (n-1 C r) 을 구해줌
        return answers[r][k];
    }
}

int main(void)
{
    cin >> n >> m;
    check(n, m);
    cout << answers[n][m] << '\n';
}