백준 1010번 :다리놓기 [2]

문제 유형 : 다이나믹 프로그래밍 ,조합(Combination)

• 다이나믹 프로그래밍 == 동적프로그래밍

  큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법

  문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생기는데 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법

• 조합 nCk : n개중 k개를 뽑을 때, 몇 개의 조합이 있는지, 순서는 고려하지 않는다.

  = n!/(n-k)!k!

---

해결방법

1. 팩토리얼을 이용하여 계산을 하면 30! 정도만 되도 int의 범위를 넘어가게 된다. 따라서 조합의 식을 조금 변형하여 범위를 넘지 않는 한에서 계산하여야 한다.

   -> nCk = nCk = n-1Ck-1 + n-1Ck 을 사용

2. 다이나믹 프로그래밍을 이용하여 같은 값을 중복하여 계산하지 않고 테이블에서 꺼내온다.

---

//1010번 다리놓기
#include <iostream>
using  std::cin;
using  std::cout;

int dp[30][30] = { 0, };		//계산한 조합을 저장

int bridge(int n, int k) {
	//nCk = n!/k!(n-k)! = nC(n-k);	//이 경우 너무 큰수가 들어와 int형으로 계산하지 못할수 있다. (팩토리얼)
	//printf("n : %d m: %d\n", n, k);	//값 확인 용

	if (dp[n][k] != 0) return dp[n][k];		//이미 계산한 값이 있으면 다시 계산하지 않고 테이블에서 꺼내와서 리턴해준다.
	if (n == k || k == 0) { // nCo
		return 1;
	}
	if (k == 1) {			//nC1
		return n;
	}
	dp[n][k] = bridge(n - 1, k - 1) + bridge(n - 1, k);		//nCk = n-1Ck-1 + n-1Ck
	return dp[n][k];
}
int main()
{
	int num;
	int n, m;
	scanf("%d", &num);
	for (int i = 0; i < num; i++) {
		scanf("%d %d", &n, &m);
		printf("%d\n",bridge(m, n));

	}

}