[백준] 1010번: 다리 놓기

 

사실상 mCn 을 구하는 문제인데, mCn 을 구하는 공식 mPn / n!을 통해서는 문제의 해답을 구할 수 없다. 문제 조건인 N <= M < 29에서 나올수 있는 최대 수인  29P29는 8.841762e+30 으로 자료형이 가질 수 있는 범위를 한참 넘어 버린다. 따라서 이 문제는 nCr = n-1Cr-1 + n-1Cr 이라는 식을 사용해서 해결해야 했다. 

 

#include <iostream>

using namespace std;


// m,n 의 조합 수 mCn
int memo[30][30];

void computeCombination()
{
	for(int i=1; i<30; i++)
	{
		memo[i][1] = i;
	}
	
	for(int j=2; j<30; j++)
	{
		for(int i=2; i<30; i++)
		{
			memo[i][j] = memo[i-1][j] + memo[i-1][j-1];
		}
	}
}

int main() {
	computeCombination();
	int t,n,m;
	cin >> t;
	for(int i=0; i<t; i++)
	{
		cin >> n >> m;
		cout << memo[m][n] << endl;
	}
}