[Python] 백준 (다리놓기) DP, 조합

---

문제풀이

• 조금 생각하다 보니 조합 문제임을 알 수 있었다.
  • n < m 이기 때문에 최대 연결할 수 있는 다리는 n개 이다.
  • m개 지역에 n개의 다리를 연결하는 경우의 수
  • 조합: 집합에서 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것이다.
  • mCn이 만들어짐
• itertools의 combinations를 쓰면 제한시간(0.5초)에 걸려 해결 할 수 없음
• 직접 만들어쓰자..!
  • 분자 denominator은 m*(m-1)*(m-2)*...*(m-n) 까지의 값
  • 분모 numerator은 n!

import sys

T = int(sys.stdin.readline().rstrip())

answer = []
for i in range(T):
    denominator = 1
    numerator = 1
    N, M = map(int,sys.stdin.readline().split())
    
    for i in range(N):
        denominator *= M
        M -= 1

    temp = N

    for i in range(N):
        numerator *= temp
        temp -= 1

    answer.append(denominator//numerator)

for i in answer:
    print(i)