[C++] BAEKJOON 2407 조합

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

2407번: 조합

 

문제는 아주 간단합니다.

Combination을 계산하는 문제로, 파스칼 삼각형을 이용하여 문제를 해결하려 하였습니다.

그런데 n, m의 값이 커지면 unsigned long long으로도 데이터를 전부 표현할 수 가 없어 덧셈을 문자열로 구현하였습니다.

#include <iostream>
#include <string>

using namespace std;

// nCm : pascal[i][j]
string pascal[101][101];

string add_string_num(string a, string b)
{
    int aidx = a.size() - 1;
    int bidx = b.size() - 1;
    string result = "";
    int carry = 0;

    while (aidx >= 0 && bidx >= 0)
    {
        int temp = a[aidx--] - '0' + b[bidx--] - '0' + carry;
        //int temp = stoi("123");
        result = to_string(temp % 10) + result;
        carry = temp / 10;
    }

    while (aidx >= 0)
    {
        int temp = a[aidx--] - '0' + carry;
        result = to_string(temp % 10) + result;
        carry = temp / 10;
    }

    while (bidx >= 0)
    {
        int temp = b[bidx--] - '0' + carry;
        result = to_string(temp % 10) + result;
        carry = temp / 10;
    }
    if (carry)
        result = to_string(carry) + result;
    return result;
}

int main()
{
    int n, m;
    cin >> n >> m;

    pascal[0][0] = "1";

    for (int i = 1; i < 101; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            if (j - 1 >= 0)
                pascal[i][j] = add_string_num(pascal[i - 1][j - 1], pascal[i - 1][j]);
            else
                pascal[i][j] = pascal[i - 1][j];
        }
    }

    cout << pascal[n][m] << "\n";
}