[백준 알고리즘] 1010번 다리 놓기

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

1010번: 다리 놓기

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

 

풀이

해당 풀이로는 조합을 생각했다. 

물론 조합이 아닌 DP를 활용하는 방법이 있을 것 같긴한데 난 DP를 활용하여 Factorial을 사용할 뿐 다른 풀이에는 이용하지 않았다.

조합을 DP로 그리고 

 

강서의 포인트가 N개, 강동의 포인트를 M개라 했을 때 고등학교 조합 공식대로 라고하면 mCn의 형태가 된다. 이 때문에 Factorial을 사용하였다.

#include<stdio.h>
#include<iostream>

using namespace std;

/* 조합은 오버플로우...*/

long long Factorial(int Number) {

	if (Number == 1) return 1;


	return Number * Factorial(Number - 1);

}

int main() {

	int term;

	scanf("%d", &term);

	while (term--) {

		int left;
		int right;
		long long result;
		scanf("%d %d", &left, &right);
		//right C  left

		long long temp = 1;
		long long temp1 = 1;

		if (right == left)  result = 1; // 스팟이 각각 하나 있을 때

		// 14  C 7, 14 C 8   14 C8 , right C left
		else {
			if (right / 2 < left) {

				left = right - left;
			}
			temp1 = Factorial(left);

			while (left  > 0) {


				temp = right*temp;
				right--;
				left--;
			}




			result = temp / temp1;
		}

		printf("%lld\n", result);

	}
}

 

끝.