백준 1010 다리놓기 c++ // 수학, 조합론

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

 

1. 시행착오

1. 팩토리얼을 dp에 담으면 되지앟나?

2. long long의 범위도 벗어난다.. 오버플로우

3. 5C2 = 5*4 / 1*2 로 간소화하기 && 그때그때 나눗셈 계산 -> 오버플로 방지

 

2. 의사코드

1. 이문제는 mCn 문제로 간소화 할 수 있다.

즉, (1, 3, 4) 순서쌍 하나만 있으면 그것을 안겹치는 경우로 생각하면 된다.

 

2. nCr 간소화 버전을 코드로 구현하면 끝이다.

ex) 5C2 = 5*4*3 (m~m-2) / 1*2*3(r=1부터 위 수행횟수만큼 증가) 

 

2. 전체코드

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll tc, n,m, dp[34];

//n!의 값
ll dfs(int n) {
	//기저사례
	//!조건불만족하면 리턴! 이 return이 먼저와야함!! -> 그래야 배제가능.
	// 안그러면, 조건불만족 인데 idx==n인 경우도 유효한 경우로 카운팅됨.
	if (n==0) {
		return 1;
	}
	
	if (dp[n]!= -1) return dp[n];

	dp[n] = dfs(n - 1)*n;

	return dp[n];
}
ll fac(int n) {
	if (n == 0 || n == 1) return 1;
	else return n * fac(n - 1);

}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	memset(dp, -1, sizeof(dp));
	//dfs(30);
	//cout << dp[5];
	//return 0;
	//for (int i = 0; i < 30; ++i) cout << "dp"<<i<<": "<<dp[i] << "\n";
	cin >> tc;
	while (tc--) {
		cin >> n >> m;
		ll result = 1;
		int r = 1;
		for (int i = m; i > m - n; i--) {
			result = result * i;
			result = result / r;
			++r;
		}
		cout << result<<"\n";
	}
	return 0;
}