[백준]2407번 조합

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

2407번: 조합

문제

nCm을 출력한다.

입력

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

출력

nCm을 출력한다.

---

nCm = n-1Cm-1 + n-1Cm을 활용할 수 있다. 하지만 이 식을 long long으로 한다면 overflow가 나버리기 때문에 string으로 하여 연산을 하여야 한다.

string으로 된 배열 두 개를 더할 때 뒷자리 숫자부터 더해야 하는데 더한 숫자가 9보다 크다면 10을 뺀 후 carry를 1로 설정하여 다음 자릿수를 더할 때 활용해야 한다.

 

	#include <iostream>
	using namespace std;
	string dp[101][101];
	int n , m;
	string add(string _s1, string _s2){
	string ret = "";
	char arr[1001];
	string s1,s2;
	if(_s1.length() > _s2.length()){
	s1 = _s2;
	s2 = _s1;
	}
	else{
	s1 = _s1;
	s2 = _s2;
	}
	int len1 = s1.length();
	int len2 = s2.length();
	int diff = len2 - len1;
	int carry = 0;
	for(int i = len2 - 1 ; i >= 0 ; i--){
	if(i >= diff){
	arr[i] = s1[i-diff] + s2[i] - '0' + carry;
	if(arr[i] > '9'){
	arr[i] -= 10;
	carry = 1;
	}
	else
	carry = 0;
	}
	else{
	arr[i] = s2[i] + carry;
	if(arr[i] > '9'){
	arr[i] -= 10;
	carry = 1;
	}
	else carry = 0;
	}
	}
	if(carry == 1)
	ret += "1";
	for(int i = 0 ; i < len2 ;i++){
	ret += arr[i];
	}
	return ret;
	}
	int main (){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 1 ; i <= n ;i++){
	dp[i][0] = "1";
	dp[i][i] = "1";
	}
	if(m > n/2)
	m = n - m;
	for(int i = 2 ; i <= n ;i++){
	for(int j = 1 ; j <= i / 2;j++){
	string s = add(dp[i-1][j-1],dp[i-1][j]);
	dp[i][j] = s;
	dp[i][i - j] = s;
	}
	}
	cout << dp[n][m];
	}

view raw 2407.cpp hosted with ❤ by GitHub

---

처음에 int로 했을 때 안될 것 같아서 long long을 사용하였는데도 안되었다. 생각보다 조합의 숫자가 컸던 것이다. 그래서 string으로 하겠다는 생각을 하였고 코드를 작성하였지만 내 생각과 동일하게 코드를 작성하는 것이 힘들었다. 작은 숫자와 큰 숫자, carry의 존재 char로 숫자를 표현하는 방법 등 42서울에서 많이 했던 것인데 꽤나 고생을 하였다. 처음에 난이도를 보고 얕잡아 봐서 구상을 제대로 안했던 것이 흠이었던 것 같다.