백준 1010 다리놓기 파이썬

황예성 2022. 9. 24. 02:59

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

1010번: 다리 놓기

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

www.acmicpc.net

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

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])))#조합 연산