백준 | 다리 놓기

백준 다리 놓기 문제 풀이이다.

강을 기준으로 서쪽에 n개의 사이트, 동쪽에 m개의 사이트가 있다. (n <= m)

이때 서쪽-동쪽 사이트를 연결하는 다리가 서로 겹쳐지지 않게, n개의 다리를 짓는 방법의 수를 구해야 한다.

다리가 겹치면 안 되고, 동쪽의 사이트 수가 서쪽과 같거나 크다.

따라서 동쪽 m개 사이트 중 n개를 고른 뒤, 서쪽 n개의 사이트를 순서대로 연결해야 한다.

그러므로 결국 m개 중 n개를 선택하는 조합의 수를 구하는 문제가 된다.

참고로 n개의 원소 중 r개를 선택하는 조합의 수는 다음과 같다.

코드(정답)는 다음과 같다.

import sys


def facto(n):
    if n <= 1:
        return 1
    else:
        return n * facto(n - 1)

def combination(n, r):
    return int(facto(n) / (facto(r) * facto(n - r)))

t = int(sys.stdin.readline())
for _ in range(t):
    n, m = map(int, sys.stdin.readline().split())
    print(combination(m, n))