백준 2407 조합 (C++)

2407번: 조합

string을 활용한 조합 문제이다. 조합 자체를 구현하는 것은 어렵지 않지만 최댓값이 100이기 때문에 자료형을 long long으로 해줘도 오버플로우가 발생한다. 이를 해결하기 위해 파스칼 삼각형 점화식을 이용하여 이를 string으로 구현을 해주었다. 점화식은 아래와 같다.

nCr = n-1Cr-1 + n-1Cr

합을 해주는 부분을 string을 이용해 반복문을 통해 한자리씩 더해주어 출력해주었다. 파스칼의 삼각형 점화식을 생각 못해 굉장히 어려웠다. 난이도가 낮다고 쉽게 봤다가 큰코 다쳤다. 주의하자.

#include <iostream>
#include <algorithm>

using namespace std;

int N, M;
string dp[101][101];

string addNum(string s1, string s2) {
	string res;
	long long sum = 0;

	while (!s1.empty() || !s2.empty() || sum) {
		if (!s1.empty()) {
			sum += s1.back() - '0';
			s1.pop_back();
		}
		if (!s2.empty()) {
			sum += s2.back() - '0';
			s2.pop_back();
		}

		res.push_back((sum % 10) + '0');
		sum /= 10;
	}
	reverse(res.begin(), res.end());

	return res;
}

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

	string& ret = dp[n][r];
	if (ret != "") return ret;

	ret = addNum(combination(n - 1, r - 1), combination(n - 1, r));

	return ret;
}

void solution() {
	cout << combination(N, M);
}

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

	cin >> N >> M;

	solution();
	
	return 0;
}