[파이썬] 백준 1010 : 다리 놓기

[파이썬] 백준 1010 : 다리 놓기

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

1010번: 다리 놓기

실버 5

수학, DP, 조합론

---

다리가 겹치지 않아야한다는 것은 중복을 허용하지 않고 순서에 상관없이 선택하는 것이므로 조합으로 풀어야 한다.

nCm = m! // (m-n)! * n!이므로 이를 구현하면 간단하게 풀 수 있다.

 

import sys
def factorial(num):
    val = 1
    for i in range(1, num+1):
        val *= i
    return val
    
T = int(sys.stdin.readline())
for _ in range(T):
    N, M = map(int, sys.stdin.readline().split())

    print(factorial(M) // (factorial(M-N) * factorial(N)))

 

파이썬에 내장된 math 라이브러리를 이용하면 factorial을 그냥 끌어다 쓸 수 있다.

 

import sys
import math
    
T = int(sys.stdin.readline())
for _ in range(T):
    N, M = map(int, sys.stdin.readline().split())

    print(math.factorial(M) // (math.factorial(M-N) * math.factorial(N)))