[C++] 백준 2407 - 조합

중등교육에서 배운 nCm을 출력하는 문제이다.

하지만 여기서 n이 매우 크다면 그 수는 주체할 수 없을 만큼 커질 것이다. 

문제의 예시에서의 100C6만 하더라도 1192052400이 출력된다.

따라서 이를 long long 형태가 아닌 string으로 문제를 해결해야 한다.

그리고 떠오를 수 있는 것은 Paskal의 삼각형이다.

Paskal의 삼각형의 점화식은 nCm = n-1Cm-1 + n-1Cm 이다.

따라서 이를 재귀적으로 구해준다면 문제를 해결할 수 있다. 

#include <bits/stdc++.h>
#define endl '\n'
#define ll long long 
using namespace std;

string arr[101][101];
int n, m;

string longadd(string a, string b) {
	int sum = 0;
	string result;

	while (!a.empty() || !b.empty() || sum) {
		if (!a.empty()) {
			sum += a.back() - '0';
			a.pop_back();
		}
		if (!b.empty()) {
			sum += b.back() - '0';
			b.pop_back();
		}
		result.push_back((sum % 10) + '0');
		sum /= 10;
	}

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

string combination(int n, int m) {
	if (m == n || m == 0) {
		return "1";
	}

	string& result = arr[n][m];

	if (result != "") {
		return result;
	}

	result = longadd(combination(n - 1, m - 1), combination(n - 1, m));
	return result;
}

int main() {

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

	cin >> n >> m;

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

	return 0;

}