[백준-2407] 조합

dp 를 사용하여 빠른 시간에 조합 값을 구하는 문제였다. n과 m에 따라 값을 구하기만 하면 되는데 이 때 수의 범위가 long long 을 벗어나기 떄문에 string 으로 합을 처리해주는 로직이 필요하다.

이를 위해 밑의 코드에서는 get_sum 이라는 함수에서 string을 통해 수의 합을 표현해주어 문제를 풀 수 있었다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>


using namespace std;
typedef long long LL;
string dp[103][103];

string get_sum(string a, string b) {
	string res = "";
	char tp_str;
	int max_size = max(a.size(), b.size());
	int min_size = min(a.size(), b.size());
	int tp_int, tp_nxt = 0;

	deque<char> dq;
	for (int i = 0; i < min_size; i++) {
		tp_int = a.back() - '0' + b.back() - '0' + tp_nxt;
		if (tp_int >= 10) {
			tp_nxt = 1;
			tp_int -= 10;
		}
		else {
			tp_nxt = 0;
		}
		a.pop_back();
		b.pop_back();
		tp_str = tp_int + '0';
		dq.push_front(tp_str);
	}

	if (a.empty() && !b.empty()) {
		for (int i = min_size; i < max_size; i++) {
			tp_int = b.back() - '0' + tp_nxt;
			if (tp_int >= 10) {
				tp_nxt = 1;
				tp_int -= 10;
			}
			else {
				tp_nxt = 0;
			}
			b.pop_back();
			tp_str = tp_int + '0';
			dq.push_front(tp_str);
		}
	}
	else if(!a.empty() && b.empty()){
		for (int i = min_size; i < max_size; i++) {
			tp_int = a.back() - '0' + tp_nxt;
			if (tp_int >= 10) {
				tp_nxt = 1;
				tp_int -= 10;
			}
			else {
				tp_nxt = 0;
			}
			a.pop_back();
			tp_str = tp_int + '0';
			dq.push_front(tp_str);
		}
	}
	if (tp_nxt > 0) {
		tp_str = tp_nxt + '0';
		dq.push_front(tp_str);
	}
	while (!dq.empty()) {
		res.push_back(dq.front());
		dq.pop_front();
	}
	return res;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		dp[i][1] = to_string(i);
		dp[i][0] = "1";
		dp[i][i] = "1";
	}

	for (int i = 3; i <= n; i++) {
		for (int j = 2; j < i; j++) {
			dp[i][j] = get_sum(dp[i - 1][j - 1], dp[i - 1][j]);
		}
	}

	cout << dp[n][m];
	return 0;
}

 

 

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

2407번: 조합