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


[ 알고리즘풀이 ]

이 문제는 long long 보다 큰 수의 덧셈을 어떻게 구현할 것인가 를 물어보는 문제입니다.

long long 보다 큰 수의 덧셈 구현하는 방법을 모르신다면 아래 포스팅에서 자세히 다뤘습니다.

먼저 읽고오시면 좋을 것 같습니다.

- 큰 수의 덧셈 구현 : https://travelbeeee.tistory.com/193

 

[ 코드 ]

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

string dp[101][101] = {};

string string_add(string a, string b) {
	int sum = 0;
	string result;
	while (!a.empty() || !b.empty() || sum) {
		if (!a.empty()) {
			sum += a.back() - '0';
			a.pop_back();
		}
		if (!b.empty()) {
			sum += b.back() - '0';
			b.pop_back();
		}
		result.push_back((sum % 10) + '0');
		sum /= 10;
	}
	reverse(result.begin(), result.end());
	return result;
}


string combination(int n, int m) {
	if (n == m || m == 0)
		return "1";
	if (dp[n][m] != "")
		return dp[n][m];
	return dp[n][m] = string_add(combination(n - 1, m - 1), combination(n - 1, m));
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	cout << combination(n, m);
}

 

+ Recent posts