1010 다리 놓기 (조합론) [Silver V]

1010번: 다리 놓기 (acmicpc.net)

 

서쪽, 동쪽에 각각 N개, M개의 사이트가 주어지고 (N <= M) 최대한 많은 수의 다리를 놓는다는 것은

M개의 사이트중 N개를 선택하라는 것이고 모든 경우의 수를 구하라는 것은 이항계수 구하는 공식을 이용하라는 의미입니다.

 

이항계수 구하기

 

정답 코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

static int D[1001][1001]; 

int array[5][5] = {
	{1, 0, 0, 0, 0}, // 0개 0 개 선택
	{1, 1, 0, 0, 0}, // 1개 0, 1개 선택
	{1, 2, 1, 0, 0}, // 2개 0, 1, 2개 선택
	{1, 3, 0, 1, 0}, // 3개 0, 1, 3개 선택
	{1, 4, 0, 0, 1}, // 4개 0, 1, 4개 선택
};

void result()
{
	int N, M;
	cin >> N >> M;
	 
	for (int i = 0; i <= M; i++) {
		D[i][1] = i; 
		D[i][0] = 1;
		D[i][i] = 1;  
	}

	for (int i = 3; i <= M; i++) 
	{
		for (int j = 2; j <= N; j++) 
		{
			D[i][j] = D[i - 1][j - 1] + D[i - 1][j]; 
		}
	}
	 
	cout << D[M][N] << "\n";  
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		result();
	}


}