(1010) 다리 놓기

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

단계별로 풀어보기

17단계(조합론) 5번째

 

 

 

다리는 겹칠 수 없으므로 동쪽 M개 사이트 중 N개를 고르면 서쪽 사이트 N개와 순서대로 대응된다. 즉 C(m,n)을 구하는 문제다.

C(29,n)은 long 범위 내에 들어오지만 29!은 long 범위 바깥이므로 이전처럼 정의에 따라 계산하는 대신 다른 방법이 필요하다.

이항 계수에서 성립하는 유명한 성질인 C(n,r) = C(n-1,r-1) + C(n-1,r)을 이용했다. 이중 for문으로 O(N^2)이 걸리는 코드지만 N은 최대 30이므로 충분하다.

 

 

 

#include <iostream>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  long comb[30][30]={};
  
  for(int i=1;i<=29;i++){
    comb[i][0]= 1;
    for(int j=1;j<i;j++) comb[i][j]= comb[i-1][j-1]+comb[i-1][j];
    comb[i][i]= 1;
  }
  
  int T;
  
  cin >> T;
  
  while(T--){
    int n, m;
    
    cin >> n >> m;
    
    cout << comb[m][n] << "\n";
  }
  
  return 0;
}