문제

  • 다리의 서쪽에서 동쪽으로 건너고자 할 때 건널 수 있는 점, 도착할 수 있는 점이 주어진다. 이 때 다리를 최대한 많이 놓으려고 한다. 즉 서쪽에서는 동쪽에서 적어도 하나의 점을 선택해야 한다.
  • 이 때 각 다리는 서로 겹치게 설치 될 수 없다. 다리를 최대로 설치 할 수 있는 경우의 수를 모두 구하라.

입력

  • 첫째 줄에 테스트 케이스 T가 주어진다. 그 후 T만큼 서쪽, 동쪽의 게이트의 수가 주어진다.

출력

예제 입력
3
2 2
1 5
13 29
예제 출력
1
5
67863915

접근

  • 다리를 선택할 수 있는 방법은 무엇인가?
  • DP가 어떻게 쓰이는가?

내가 생각한 풀이

  • 겹치지 않게 선택하는 문제이므로 Combination으로 풀면 된다는 생각이 들었다.
  • 원하는 값의 Combination값을 구해주고 출력하면 끝!
    • 이 때 숫자가 커질 경우 자료형의 범위를 벗어날 수 있으므로 Combination의 특성을 이용하여 값이 자료형의 범위를 벗어나지 않게 했다.
    • 예 : 5C3 은 5C2로 나타낼 수 있음.

코드

#include<iostream>
using namespace std;
int main(void){
  int c,a,b;
  cin>>c;
  for(int i = 0 ;i<c;i++){
    cin>>a>>b;
    int iter;
    if(a>(b/2)) iter = b-a;
    else iter = a;
    unsigned long long r=1, d=1;
    for(int j = 0 ;j<iter;j++) r*=(b-j);
    for(int k = 1 ;k<=iter;k++) d*=k;
    cout<<r/d<<endl;
  }
  return 0;
}