[백준 C++] 2407번 : 조합

1. 문제

 

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

2407번: 조합

 

2. 알고리즘 분류

• 수학
• 조합론
• 임의 정밀도 / 큰 수 연산

 

3. 소스 코드

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

// 조합 계산 결과 테이블
string table_combi[105][105];

// 큰 수 더하는 함수
// num1, num2의 수는 거꾸로 저장되어있음 ex) 123 => "321"
string add(string num1, string num2) {
	string ans = "";
	int sum = 0;
	int size = max(num1.size(), num2.size());

	// num1, num2 중 큰 수의 자리 수까지 계산
    // 만약 자리수가 커지는 경우, sum이 있는지 확인한 후 더 추가적으로 계산
	for (int i = 0; i < size || sum; i++) {
    
    	// sum = 이전 자리수에서 10보다 커져서 넘어온 수
        // 각 num의 수 들을 더하기
		if (num1.size() > i) sum += num1[i] - '0';
		if (num2.size() > i) sum += num2[i] - '0';

		// sum의 값을 ans에 저장
		ans += sum % 10 + '0';
        
        // sum의 값이 10을 넘었을 경우, 다음 자리 수로 넘겨주기
		sum /= 10;
	}

	return ans;
}

// 조합 구하는 함수
string Combi(int n, int m) {
	// nCn = 1, nC0 = 1
	if (n == m || m == 0) return "1";
    
    // 조합 테이블에 값이 저장되어있을 경우, 불러오기
	if (table_combi[n][m] != "") return table_combi[n][m];

	// nCm = n-1Cm-1 + n-1Cm
	return table_combi[n][m] = add(Combi(n - 1, m - 1), Combi(n - 1, m));
}

int main() {
	int n, m;
	cin >> n >> m;
	
    // nCm 값 구하기
	Combi(n, m);

	// nCm 결과 값이 거꾸로 저장되어있으므로, 문자열 맨 뒤부터 출력
	for (int i = table_combi[n][m].size() - 1; i >= 0; i--) {
		cout << table_combi[n][m][i];
	}

	return 0;
}

 

4.  상세 설명

1. nCm = n-1Cm-1 + n-1Cm 식을 통해 nCm을 계산(재귀 함수 이용)
2. 속도 향상을 위해 각 계산한 조합 값을 테이블에 저장
3. 큰 수를 계산하기 위해 문자열로 변경 후, 계산

 

5.  문법

5.1)  조합의 수 구하기

int table_combi[100][100];

int combi(int n, int m) {
	if (n == m || m == 0) return table_combi[n][m] = 1;
    if (table_combi[n][m] != 0) return table_combi[n][m];
    
    return table_combi[n][m] = combi(n-1, m-1) + combi(n-1, m);
}

 

5.2)  문자열을 이용해 큰 수 더하기

string add(string num1, string num2) {
	string ans = "";
	int sum = 0;
	int size = max(num1.size(), num2.size());

	for (int i = 0; i < size || sum; i++) {
		if (num1.size() > i) sum += num1[i] - '0';
		if (num2.size() > i) sum += num2[i] - '0';

		ans += sum % 10 + '0';
		sum /= 10;
	}

	return ans;
}