[C++]BOJ 1010 - 다리 놓기

보자마자 떠오른것은 조합이다.
mCn을 계산하면 정답이 나오지만 m이 최대 29까지 등장하기 때문에 계산 과정에서 29!을 계산할 여지가 있다.
29!은 long long에도 못들어가는 아무튼 엄청 크다.
이를 해결하는 방법은 여러가지가 있다.

먼저 조합의 성질을 보자.
nCr이라면 n! / {(n - r)! * r!} 이다.
이 때문에 r을 n - r로 바꾸어 계산해도 정답은 일치한다.
그렇다면 주어진 범위에서 계산 과정 중 분자의 크기가 가장 커지게 만드는 경우는 n이 29일 때와 r이 14또는 15일 때 이다.
수식을 약분하면 계산 과정 중 등장할 가장 큰 수인 29!/15!은
6,761,440,164,390,912,000
이고 long long의 양수 최대범위는
9,223,372,036,854,775,807
이다.


아슬아슬하게 걸친다.
가장 큰 수가 오버플로우가 발생하지 않는다면 주어진 범위 내의 모든 수도 계산하는데 문제가 없을 것이다.

위 내용을 코드로 나타내면 아래와 같다.

#include <iostream>
using namespace std;
long long t, n, m, ans;
int main() {
	cin >> t;
	while(t--) {
		ans = 1;
		cin >> n >> m;
		n = n > m - n ? m - n : n; // m - n과 n중 더 작은것을 사용한다.
		for(int i = 0; i < n; i++)
			ans *= m - i;
		for(int i = 2; i <= n; i++)
			ans /= i;
		cout << ans;
	}
}

또 다른 방법은 조합 계산을 동적 계획법을 이용해 재귀함수로 구현하는 것이다.
그 전에 조합 nCr = n-1Cr-1 + n-1Cr로 나타낼 수 있다는 것을 알아야 한다.(파스칼의 삼각형으로 부터 유래되었다.)
로또로 예를 들어 보면 45개 중 6개를 뽑을 때의 경우의 수는 1번 공을 미리 뽑고 5개를 랜덤으로 뽑는 경우와 1번 공을 제외하고 6개를 랜덤으로 뽑는 경우를 더한 것과 같다.
저 공식을 사용해 계속 쪼개나가서 n과 r이 같아지거나 r이 0이 될 때 1을 반환하면 된다.

#include <iostream>
using namespace std;
int t, a, b, dp[31][31];
int cbn(int n, int r) {
	if(n == r || r == 0) return 1;
	if(dp[n][r]) return dp[n][r];
	return dp[n][r] = cbn(n - 1, r - 1) + cbn(n - 1, r);
}
int main() {
	cin >> t;
	while(t--) {
		cin >> a >> b;
		cout << cbn(b, a) << endl;
	}
}