[성실코딩 16일차] 백준 #1010 다리 놓기 / DP 조합 **

쉬운 문제라고 생각했는데 

세번째 예제 케이스에서 0으로 답을 출력했다. 

뭐가 문제인지 생각해봤는데

unsigned long long result = factorial(m) / factorial(m - n) / factorial(n);

다음 코드에서 long long 은 정수형이니까 정확하게 나눠지지않고 (소수점이 버려짐), 그거에 따라 오차가 발생한다. 

따라서 factorial(m-n)을 먼저 나누는지, factorial(n)을 먼저 나누는지에 따라 결과값도 달랐음.

해결책은 질문검색에서 봤는데, 점화식을 계산하는 방식으로 해보라고했다.

C(n,m) = C(n-1,m) + C(n-1,m-1) 

즉, DP 메모제이션으로 풀라는 말 같다. 

오늘말고 다음에 해봐야겠다......

일단, 틀린 코드라도

#include <iostream>

using namespace std;

unsigned long long DP[30] = { 0, }; //1~29

long long factorial(int _v) {
	if (_v==0) { // 0
		return 1; // 0으로 나눌 수 없기 때문에
	}
	if (_v==1) {
		return DP[_v] = 1;
	}
	if (DP[_v] != 0) {
		return DP[_v];
	}
	else {
		return DP[_v] = factorial(_v-1)* _v;
	}
}

int main() {

	// 입력
	int tc;
	cin >> tc;
	for (int i = 0; i < tc; i++) {
		int n, m;
		cin >> n >> m;
		
		unsigned long long result = factorial(m) / factorial(m - n) / factorial(n);

		cout << result << endl;
	}
	
	return 0;
}