백준 1010 다리놓기 파이썬

 

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

1010번: 다리 놓기

꼬이지 않게 다리를 배치하기 위해서 조합을 사용하는 되는 문제였다.

from itertools import combinations
n,m = map(int,input().split())
n,m = min(n,m),max(n,m)
s=list(combinations([i for i in range(m)], n))
print(len(s))

위와 같은 방법으로 조합을 만들어서 계산하게 되면 시간초과가 발생함으로

조합계산법으로 구현했다. (조합 계산에 필요한 팩토리얼은 fac DP를 만들어 저장해뒀다.)

fac=[1]*31#팩토리얼을 담아두는 DP
for i in range(1,31):
    fac[i]=fac[i-1]*i
for _ in range(int(input())):
    n,m = map(int,input().split())
    n,m = min(n,m),max(n,m)
    print(int(fac[m]/(fac[m-n]*fac[n])))#조합 연산