백준 2407 조합

1. 문제 링크

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

2407번: 조합

 

2. 풀이

파스칼의 삼각형에서 제시하는 점화식을 활용해 DP방식으로 풀 수 있다.

문제는 long long 타입조차 감당 안될 정도로 숫자가 커진다는 것.

따라서 숫자 표현을 string으로 해야 한다.

 

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int n, m;

string arr[101][101];

string StringPlus(const string& s1, const string& s2) {
	string result = "";
	int tmp;
	auto iter1 = s1.rbegin();
	auto iter2 = s2.rbegin();
	int prev = 0;
	while (iter1 != s1.rend() && iter2 != s2.rend()) {
		tmp = (*iter1 - '0') + (*iter2 - '0') + prev;
		result.push_back((tmp % 10) + '0');
		prev = tmp / 10;
		iter1++; iter2++;
	}
	while (iter1 != s1.rend()) {
		tmp = (*iter1 - '0') + prev;
		result.push_back((tmp % 10) + '0');
		prev = tmp / 10;
		iter1++;
	}

	while (iter2 != s2.rend()) {
		tmp = (*iter2 - '0') + prev;
		result.push_back((tmp % 10) + '0');
		prev = tmp / 10;
		iter2++;
	}

	if(prev != 0)
		result.push_back(prev + '0');

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

int main() {
	cin >> n >> m;
	for (int i = 0; i <= 100; i++) {
		arr[i][0] = "1";
		arr[i][i] = "1";
	}

	for (int i = 2; i <= 100; i++) {
		for (int j = 1; j < i; j++) {
			//arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
			arr[i][j] = StringPlus(arr[i - 1][j - 1], arr[i - 1][j]);
		}
	}

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