백준 2407번

 

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

2407번: 조합

 

문제 접근 과정:

1)알고리즘 선택: 

 

조합은 dp알고리즘 예제로 유명한 문제여서 고민 없이 알고리즘을 선택했다.

고등학교 수학에서 배운 nCk= n-1Ck + n-1Ck-1 식을  이용해 dp점화식을 dp[i][j]=dp[i-1][j]+dp[i-1][j-1]으로 정하였다.

 

2) dp배열의 자료형:

dp배열에 저장될 수 있는 가장 큰 값 100C50으로 longlong의 범위를 넘개 된다.

(처음에는 longlong이겠거니 하고 풀어서 틀렸다. 항상 자료형 결정에 대해 간관하지 말자!) 

 

3) string으로 더하기:

string은 문자열이기에 더하기를 하려면 각 자리별로 덧셈을 처리해야한다.

이때 올림수도 꼭 반영해주어야한다.

 

m=m(올림수) + 두수의 같은 자리의 합 으로 올림수를 반영해 주었다.

해당 계산의 결과 m을 m%10으로 처리하여 두수의 각 자리의 덧셈 결과를 저장해주고 다음 계산에 사용될 올림수를 m/10으로 구하였다.

 

*두수의 최대 자리수가 다른 경우도 생각해 주어야한다.(코드 참조)

*덧셈 결과를 저장하는 string은 역순으로 저장 돼있다. 이를 reverse 함수를 통해 해결하였다. 

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string dp[101][101];

string cal(string a, string b) {
	string sub;//계산 결과를 저장하는 string
	int m = 0;
	if (a.size() > b.size()) { //최대 자리수가 작은 수를 항상 a로 한다.
		swap(a, b);
	}

	for (int i = 0; i < a.size(); i++) { //두수의 각 자리 덧셈

		//올림 수를 반영해 각 숫자의 같은 자리수를 계산한다.
		m = m + (a.back() - '0') + (b.back() - '0'); 
		a.pop_back(); 
		b.pop_back();

		sub.push_back((m%10)+'0');
		m = m / 10; //올림수 구하기

	}

	//만일 두 수의 최대 자리수가 다를 경우 
	//즉 b의 자리수가 더 클 경우( 항상 b는 a보다 크거나 같다)  
	while (b.size()) {
		m = m + (b.back() - '0');
		b.pop_back();
		sub.push_back((m % 10) + '0');
		m = m / 10;	
	}

	//마지막 올림수가 있을 경우 반영해준다.
	if (m == 1) {
		sub.push_back('1');
	}

	//덧셈 결과가 반대 순서로 저장됐기 때문에 reverse 함수를 통해 이를 바꿔준다.
	reverse(sub.begin(), sub.end());
	return sub;
}
int main() {
	int num, index;
	cin >> num >> index;

	for (int i = 1; i <= num; i++) {
		dp[i][0] = '1';
		for (int j = 1; j < i; j++) {
			dp[i][j]=cal(dp[i - 1][j - 1], dp[i - 1][j]);
		}
		dp[i][i] = '1';
	}
	cout << dp[num][index];
	
}