백준 2407 조합 c++ (조합,dp,파스칼의 삼각형, 문자열)

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

2407번: 조합

문제

nCm을 출력한다.

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

출력

nCm을 출력한다.

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 조합론
• 임의 정밀도 / 큰 수 연산

풀이

파스칼 삼각형 : https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95

 

조합+dp+문자열 문제이다.

우선 nCr은  n!/r!*(n-r)!로 구할 수 있지만, 문제에선 입력값이 n 100 r 100이므로 long long 범위를 초과한다.

이러한 경우 보통 string을 이용하는데 이 문제에서도 그렇다.

 

우선,

0C0= 1

1C0= 1, 1C0 = 1

2C0 = 1, 2C1 = 2, 2C2 = 1

3C0 = 1, 3C1 = 3, 3C2 = 3, 3C3 =1

4C0 = 1, 4C1 = 4, 4C2 = 6, 4C3 = 4, 4C4 =1

이다.

위의 결과를 보면 파스칼의 삼각형과 결과가 같다는 것을 알 수 있다.

파스칼 삼각형의 알고리즘의 점화식은

dp[n][r] = dp[n-1][r-1] + dp[n-1][r] 이고,

n과 r이 같거나, r이 0이라면 모두 1이다.

이렇게 0,0부터 n,r까지 조합의 수를 파스칼의 삼각형으로 구할 수 있는데, 이 숫자는 long long의 범위를 초과하므로, 문자열로 덧셈을 해주어야 한다.

문자열 덧셈은 두 문자열의 길이를 맞춰주고 구현하는 것이 편하다.

 

코드

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

int n, m;

string combi[101][101];

string addNum(string a, string b) {
	string result="";
	if (a.length() > b.length()) {
		while (a.length() != b.length()) {
			b = '0' + b;
		}
	}
	else {
		while (a.length() != b.length()) {
			a = '0' + a;
		}
	}
	int sum = 0;
	for (int i = a.length()-1; i >=0; i--) {
	
		sum += a[i] - '0';
		sum += b[i] - '0';
		
		result = to_string(sum % 10) + result;
		if (sum >= 10) {
			
			sum = 1;
		}
		else {
			sum = 0;
		}
	}
	if (sum == 1) {
		return '1' + result;
	}

	return result;
}

void makeCombi() {
	combi[0][0] = "1";
	combi[1][0] = combi[1][1] = "1";
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (i == j || j==0) {
				combi[i][j] = "1";
			}
			else {
				combi[i][j] = addNum(combi[i - 1][j - 1], combi[i - 1][j]);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	makeCombi();
	cout << combi[n][m];

	return 0;
}