백준 2407번 조합 C++

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

 

파이썬으로 하면 그냥 계산하면 되지만 C++에서는 int64 범위를 넘어가기 때문에 문자열로 처리해야 한다.

조합 계산은 파스칼의 삼각형을 이용해 메모이제이션과 재귀 방식을 이용하였고 수를 더할때는 문자열을 이용하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using ll = long long;

vector<vector<string>> cache;

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

	string& ret = cache[n][m];
	if (ret != "")
		return ret;

	string left = Combination(n - 1, m - 1);
	string right = Combination(n - 1, m);

	int maxLength = max(left.length(), right.length());
	if (left.length() < maxLength) {
		int length = left.length();
		for (int i = 0; i < maxLength - length; i++) {
			left = " " + left;
		}
	}
	if (right.length() < maxLength) {
		int length = right.length();
		for (int i = 0; i < maxLength - length; i++) {
			right = " " + right;
		}
	}
	stack<string> st;
	int up = 0;
	for (int i = maxLength - 1; i >= 0; i--) {
		int num = up;
		if (left[i] != ' ') {
			num += left[i] - '0';
		}
		if (right[i] != ' ') {
			num += right[i] - '0';
		}
		if (num >= 10) {
			up = 1;
			num -= 10;
		}
		else {
			up = 0;
		}
		st.push(to_string(num));
	}
	if (up == 1)
		st.push("1");
	while (!st.empty()) {
		ret += st.top();
		st.pop();
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cache = vector<vector<string>>{ 101,vector<string>(101,"") };
	int n, m;
	cin >> n >> m;
	cout << Combination(n, m);
};