[python] 1010. 다리놓기

문제 출처

1010. 다리놓기

 

풀이

단순한 순열/조합을 사용한 경우의 수 문제이다. 서쪽에서 동쪽으로 다리를 놓을때 두 개 이상의 다리가 겹치면 안되므로 순서를 배제한 모든 경우의 수를 구하면 된다.

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

    tot = 1         # 동쪽과 서쪽의 사이트 갯수가 동일할때
    if N != M:      # 동쪽의 사이트 갯수가 더 많을때
        for i in range(M, M-N, -1):
            tot *= i
        for i in range(N, 1, -1):
            tot //= i
    print(tot)