백준 2407 - 조합(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2407

2407번: 조합

결과 값이 매우 크기에, 문자열을 통한 계산을 해야하는 문제입니다.

nCr = n-1Cr-1 + n-1Cr 을 통해 조합 값을 구할 수 있습니다.

nCm의 최댓값은 long long int의 범위를 넘어설 수 있습니다. 따라서 문자열을 통해 합을 계산하고 저장해야합니다.

사진을 통해 알 수 있는 점은 nCr의 값은 n-1Cr-1 + n-1Cr 을 통해 구할 수 있다는 것입니다.

 

위의 공식을 통해 값을 나눠가며 구하면 됩니다.

값을 나눴을 때, N의 값과 M의 값이 같아지거나, M의 값이 0이면 "1"을 return 해주면됩니다.

nCm의 값이 이미 구해져있으면, 해당 값을 바로 return 해줍니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>
#define INF 987654321

using namespace std;

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

string big_number_add(string x, string y) {
	int sum = 0;
	string ans;
	while (!x.empty() || !y.empty() || sum) {
		if (!x.empty()) {
			sum += x.back() - '0';
			x.pop_back();
		}
		if (!y.empty()) {
			sum += y.back() - '0';
			y.pop_back();
		}
		ans.push_back(sum % 10 + '0');
		sum /= 10;
	}
	reverse(ans.begin(), ans.end());
	return ans;
}

string Find_ans(int x, int y) {
	if (x == y || y == 0) return "1";
	string &sum = combination[x][y];
	if (sum != "") return sum;
	sum = big_number_add(Find_ans(x-1, y-1), Find_ans(x-1,y));
	return sum;
}

void solve() {
	string ans = Find_ans(N, M);
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요