[C/C++] 백준 1010번 - 다리 놓기

 

 

<코드>

#include<iostream>
#include<algorithm>
using namespace std;

int dp[30][30];
int T, N, M, ans;

int main()
{
	cin >> T;

	dp[0][0] = 1;
	dp[1][0] = 1;
	dp[1][1] = 1;

	for (int i = 2; i < 30; i++)
		for (int j = 0; j <= i; j++)
		{
			if (j == 0 || j == i) dp[i][j] = 1;
			else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
		}

	while (T--)
	{
		cin >> N >> M;
		cout << dp[M][N] << endl;
	}
	
}

 

 

풀이 방법

파스칼 삼각형

조합의 점화식

 

조합의 공식에 따라서 팩토리얼을 구한 뒤 계산하는 방법은 숫자가 기하급수적으로 커지므로..(13!만 되도 62억) dp로 30x30 배열을 생성한 뒤 점화식을 이용하여 dp값들을 채워 나간 뒤 N, M값을 입력받아 dp[M][N]값을 출력하였다.

 

dp 배열에 저장된 값들

 

www.acmicpc.net/problem/1010

1010번: 다리 놓기