Lee's Programming Practice

알고리즘 문제 풀이

문제

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

풀이

조합에서 사용되는 파스칼의 삼각형을 이용한 DP 방식으로 접근한다.

점화식은 DP[i][j] = DP[i-1][j] + DP[i-1][j-1];

생각해야할 부분으로, 100 C 5 조합같은 경우는 long long int 자료형을 초과하는 범위이므로, 문자열을 사용하여 해결해야한다. 문자열 덧셈 함수와 파스칼 삼각형을 이용한 조합 함수 1개를 만들어서 풀이하였다.

소스 코드

// 헤더파일
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <cctype>
#include <set>
#include <string.h>

using namespace std;

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

string b_add(string s1, string s2) {
	int sum = 0;
	string r;

	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();
		}
		
		r.push_back((sum % 10) + '0');
		sum /= 10;
	}

	reverse(r.begin(), r.end());
	//cout << r << '\n';
	return r;
}

void comb() {
	for (int i = 2; i <= N; i++) {
		for (int j = 0; j <= M; j++) {
			if (i == j || j == 0)
				arr[i][j] = "1";
			else
				arr[i][j] = b_add(arr[i - 1][j - 1], arr[i - 1][j]);
		}
	}
}

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

	cin >> N >> M;

	arr[0][0] = "1";  arr[1][0] = "1"; arr[1][1] = "1";
	comb();
	cout << arr[N][M];
}