백준 2407 (조합) c++

문제

2407번: 조합

n과 r을 입력받아 nCr 을 출력하면 되는 문제입니다. n과 r은 범위가 100까지 입니다.

단순히 계산하게 되면 오버플로우가 발생합니다. 

따라서 string 형으로 계산을 해줘야 합니다. 

조합을 구하는 방식은 '파스칼의 삼각형' 방식을 이용해 문제를 해결하였습니다.

nCr = (n-1)C(r-1) + (n-1)C(r) 입니다.

먼저 위와 같은 방식으로 dp 형태로 nCr을 계산할 예정입니다.

string arr[101][101]
string combination(int n, int r) {
	if (n == r || r == 0) //nCn =1 , nC0 = 1
		return "1";

	string& ans = arr[n][r]; 
	if (ans != "") //이미 계산했던 dp이면 그대로 return
		return ans;

	return ans = cal(combination(n - 1, r - 1), combination(n - 1, r));
	
}

모든 계산은 문자열로 이루어 집니다. 

 

이제 점화식 arr[n][r] = arr[n-1][r-1] + arr[n-1][r] 을 위해 더하는 과정이 필요합니다.

string cal(string st1, string st2) {
	int sum = 0;
	string result;
	while (!st1.empty() || !st2.empty() || sum) {
		if (!st1.empty()) {
			sum += st1.back() - '0';
			st1.pop_back();
		}
		if (!st2.empty()) {
			sum += st2.back() - '0';
			st2.pop_back();
		}
		result.push_back((sum % 10) + '0'); //일의자리 부터 push
		sum /= 10;
	}
	reverse(result.begin(), result.end()); //일의 자리가 맨 앞이므로 reverse
	return result;
}

문자열 2개를 합쳐주는 과정입니다. 일의 자리 부터 하나씩 %10을 계산해 일의자리 부터 서로 더해줘

result에 넣어줍니다. 

마지막에는 일의 자리가 맨앞에 있는 상태이므로 reverse를 해줘서 return하게 됩니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
string arr[101][101];
string combination(int n, int r);
string cal(string st1, string st2);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n, r;
    cin >> n >> r;
 
    cout<< combination(n, r);
    
    
 
    return 0;
}
string combination(int n, int r) {
    if (n == r || r == 0)
        return "1";
 
    string& ans = arr[n][r];
    if (ans != "")
        return ans;
 
    return ans = cal(combination(n - 1, r - 1), combination(n - 1, r));
    
}
string cal(string st1, string st2) {
    int sum = 0;
    string result;
    while (!st1.empty() || !st2.empty() || sum) {
        if (!st1.empty()) {
            sum += st1.back() - '0';
            st1.pop_back();
        }
        if (!st2.empty()) {
            sum += st2.back() - '0';
            st2.pop_back();
        }
        result.push_back((sum % 10) + '0');
        sum /= 10;
    }
    reverse(result.begin(), result.end());
    return result;
}