백준 1010번: 다리 놓기 python

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

문제

'사이트' 라고 하는 것이 강을 기준으로 왼쪽,오른쪽에 있다.
왼쪽을 N개 오른쪽을 M개라고 했을 때 N <= M 개가 있고
그림처럼 교차되는 경우가 없게끔 다리를 짓고 싶을 때
N,M을 주어줬을 때 지을 수 있는 다리의 경우의수를 구하는 문제.

접근 방식

다리를 연결한다는 개념말고 그냥 강 오른쪽에 M개의 사이트 중에서 N개를 고르면 그 N개의 사이트가 왼쪽 N개와 연결된다고 생각하면 쉽다.

이 경우 mCn 이 된다.
조합 공식은 m! / (m-n)!n! 으로 이항 계수 에서 다뤘으니 참고하면 되겠다.

def factorial(n):
    num = 1
    for i in range(1, n+1):
        num *= i
    return num


T = int(input())

for _ in range(T):
    n, m = map(int, input().split())
    bridge = factorial(m) // (factorial(n) * factorial(m - n))
    print(bridge)