백준 - 1010 (Python) - 다리 놓기

백준 1010

다리 놓기

이항 계수(n개의 원소를 가지는 집합에서 k개의 부분집합을 고르는 조합의 경우의 수)를 사용하여 푸는 문제.

저번 포스팅에선 math 모듈을 사용해서 풀었으니 이번엔 모듈을 사용하지 않는 코드로..

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)

m이 n보다 크기 때문에 최대 연결할 수 있는 다리의 개수는 n개이고
m개의 지역에 n개의 다리를 놓을 수 있는 경우의 수를 구하는 것이기 때문에
mCn 으로 표현할 수 있고 이는 m! 을 (m-n)!n! 으로 나눈 값이 된다.