[백준 1010번] 다리 놓기 - python

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

📌 문제 탐색하기

목표

• 다리를 지을 수 있는 경우의 수를 구해보자.
• 다리는 반드시 N개를 지어야 하고 교차되지 않아야한다.
• 한 사이트에는 최대 한 개의 다리만 연결이 가능하다.

입력값

• 서쪽 사이트: N
• 동쪽 사이트: M (N ≤ M)
• ex)
• 3 2 2 1 5 13 29

출력값

• 다리를 지을 수 있는 경우의 수를 출력한다.
  • ex)
  • 1 5 67863915

📌 코드 설계하기

해결 아이디어

• 교차되지 않게 다리를 짓는 방법의 수 → 조합 문제
• 결국, M개의 동쪽 사이트 중에서 N개를 선택하는 경우의 수와 동일하다.
• 따라서 mCn = m! / (n! · (m-n)!)

📌 정답 코드

import sys

def fac(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

t = int(sys.stdin.readline())

for i in range(t):
    n, m = map(int, input().split())
    result = fac(m) // (fac(n) * fac(m-n))
    print(result)

최종 시간 복잡도: O(min(N, M-N))