1010 - 다리 놓기

 

---

 

문제

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

1010번: 다리 놓기

 

풀이

 

 

사실 이 문제랑 똑같다

해당문제는 조합의 경우의 수를 구하면 바로 해결되는 문제이다. 

 

 

위의 식을 고대로 구하면 답이 나온다. 단 팩토리얼은 DP로 미리 다 계산해둔다음 풀면 쉽게 풀 수 있다.

 

코드

d = [1] * 31

d[0] = 1
d[1] = 1
for i in range(2, 31):
    d[i] = d[i-1] * i

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    print(d[m] // (d[n] * d[(m-n)]))