[백준 알고리즘: python 3] #1010 - 다리 놓기

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

 

조합 문제가 계속 보이네요! 1010번 문제는 단순한 조합의 수 구하기 문제입니다. 아마 고등학교 함수 시간에 X, Y에서의 좌표를 각각 주고 존재할 수 있는 함수의 개수를 찾아라! 라는 문제를 보셨을 것 같은데요, 완전히 동일한 문제입니다.

 

Hint!

단순히 강의 오른쪽의 M개의 사이트들 중에서 N개을 고르시고 왼쪽의 N개의 사이트와 겹치지 않게, N개의 다리를 놓을 수 있는 단 하나의 방법이 나옵니다. 그냥 나란히 연결하는 것이죠. 즉, 핵심은 M개의 사이트 중 N개를 고르는 경우의 수를 구하는 것이고 이전 문제 벡터 매칭에서도 사용했던 조합(combination)의 수를 구하는 문제입니다. 

 

이번에는 조합 공식을 찾아 직접 함수를 만들어 사용했습니다. 저번에 사용했던 itertools.combinations() 함수는 개수를 반환하는 것이 아니라 모든 조합의 수를 튜플로 친절하게 담아두니, 이번엔 그럴필요는 없습니다. (느려요!)

 

이 코드로 풀이하였습니다.

 

import math

def nCr(n, r):
    f = math.factorial
    return f(n) / (f(r) * f(n-r))

T = int(input())
results = []

for _ in range(T):
    N, M = map(int, input().split())
    results.append(int(nCr(M, N)))

for result in results:
    print(result)