(cpp) Baekjoon 2407번 문제 ‘조합’ - 수학, 조합론, 임의정밀도/큰수연산

20 Feb 2023 on Programming Languages

Baekjoon 2407번 문제 ‘조합’ - 수학, 조합론, 임의정밀도/큰수연산

---

문제

문제풀이

코드

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

string table[105][105];

string A(string num1, string num2){
	long long int sum = 0;
	string result;
	while (!num1.empty()||!num2.empty()|| sum!=0) {
		if (!num1.empty()) {
			sum += num1.back()-'0';
			num1.pop_back();
		}

		if (!num2.empty()) {
			sum += num2.back()-'0';
			num2.pop_back();
		}
		result.push_back((sum % 10)+'0');
		sum = sum / 10;

	}
	reverse(result.begin(), result.end());
	return result;
}

string combi(int n,int m) {
	if (n == m || m == 0) {return "1";}
	
	if (table[n][m] != "") {return table[n][m]; }//table에 값이 있으면 가져다 쓰기

	table[n][m] = A(combi(n - 1, m - 1), combi(n - 1, m));
	return table[n][m];
}

int n, m;
int main() {
	cin >> n >> m;
	cout << combi(n, m);
}

• 조합 구하는 부분과 문자열로 큰 수 더하는 부분을 나눠서 생각해야 한다.
• 두 개의 combination을 더해주는 A 함수의 input은 문자이다. 따라서, 1+1=2이 아닌, “1”+”1” = “11”이다.
• 문자를 숫자처럼 더하는 과정은 문제풀이의 두 번째 그림 참조. 더할 때 자릿수가 넘어가는 부분을 처리하는 것이 어려웠다.
• combination함수를 재귀적으로 호출하는 과정 중에도 A함수를 사용하므로, 마지막에만 reverse해주는 것이 아닌, A함수에서 reverse를 해주어야 한다.