2022.02.28 [백준] (python 파이썬) 다리 놓기

 

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

1010번: 다리 놓기

---

풀이

이 문제는 M개의 사이트에서 N개를 뽑아 N의 사이트와 연결시키는 문제이다.

하나의 사이트에 하나의 사이트만 연결할 수 있고 서로 겹치면 안되므로 조합을 이용하여 쉽게 해결할 수 있다.

참고로 조합은 M!/(N!*(M-N)!)이다.

아래의 코드에서 N,M의 범위가 30이하이므로 30까지의 팩토리얼 값을 factorial배열에 담았다.

그리고 주어진 조건에 맞게 조합을 이용하여 연결할 수 있는 가지수를 구했다.

factorial=[1]*31
for i in range(1,31):
    factorial[i]=factorial[i-1]*i
for _ in range(int(input())):
    n,m=map(int,input().split())
    ans=factorial[m]//(factorial[n]*factorial[m-n])
    print(ans)