알고리즘: 백준 1010번 다리놓기 (feat. c++)

백준 1010번 링크입니다. 

1010번: 다리 놓기

 

 

 

n개 중에 r개를 고르면 되므로 nCr을 사용하면 간단하다...고 생각했지만

 

아니였다.

 

팩토리얼을 다이나믹 프로그래밍으로 구해서 콤비네이션하려 했지만 

 

long long 자료형을 써도 넘어가버려서 

 

다이나믹 프로그래밍과 재귀함수를 이용하였다.

 

nCr = n-1Cr-1 + n-1Cr 을 이용해서

 

recursive form을 만들어 해결하였다. 

 

 

 

#include<iostream>
using namespace std;

int cache[30][30];
// 다이나믹 프로그래밍의 테이블

int recurseive_comb(int n, int r)
{//recursuve form

	if (n == r) {  //base case
		return 1;
	}
	else if (r == 0) {
		return 1;
	}
	else if (r == 1) {
		return n;
	}


// 만약 값이 존재하면 바로 리턴
	if (cache[n][r] != NULL)
	{
		return cache[n][r];
	}


//값이 존재하지 않는다면 재귀를 이용해서 값을 만들어준다. 
	cache[n][r] = recurseive_comb(n - 1, r - 1) + recurseive_comb(n - 1, r);
	
	return cache[n][r];

}



int main() {

	int T;
	cin >> T;
	
	int** cases = new int*[T];
	
	for (int i = 0; i < T; i++) {
		cases[i] = new int[2];
		cin >> cases[i][0];
		cin >> cases[i][1];
	}
	

	for (int i = 0; i < T; i++) {
		cout << recurseive_comb(cases[i][1], cases[i][0])<<endl;
	}



	return 0;
}