백준 1010 다리놓기

https://www.acmicpc.net/problem/1010

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 강의 서쪽에 N개의 다리가 있고 강의 동쪽에 M개의 다리가 있을 때 연결 할 수 있는 경우의 수를 출력해야 합니다.

 

테스트 케이스가 여러가지이므로 한번에 답을 다 구해놓고 그에 맞게 출력하도록 해야 하는데 

 

M개중에 N개를 선택하는 조합으로 볼 수 있습니다. 즉 mCn으로 볼 수 있고 이는 mCn = m-1Cn-1 + m-1Cn 으로 나타낼 수 있습니다. 따라서

 

이에따라 모든 최대 경우까지 값을 모두 구하면 됩니다.

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int T,N,M;
	int arr[31][31] = {0, };
	
	for(int i = 1; i < 31; i++) {
		arr[i][i] = 1;
		arr[i][0] = 1;
	}
	
	for(int i = 2; i < 31; i++) {
		for(int j = i - 1; j > 0; j--)
			arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
	}
	
	cin >> T;
	
	while(T--) {
		cin >> N >> M;
		cout<<arr[M][N]<<'\n';
	}
	return 0;	
}