[백준] 1010번 다리 놓기 (Python)

문제

www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

코드

def fac(a):
    if a==0:
        return 1
    if a==1:
        return 1
    else:
        return a * fac(a-1)

# nCk = n! / ((n-k)! * k!)

T = int(input())
for i in range(T):
    n, m = map(int, input().split()) # m개점중에서 n개를 선택하는 경우의수. mCn
    print(fac(m) // (fac(m-n) * fac(n))) 

 

코드설명

m개의 점에서 n개를 선택하는 경우의 수는 mCn 이다.

nCk = n! / ((n-k)! * k!)

 

공식을 이용해 풀기위해서 팩토리얼 함수를 구현해주고 함수를 호출하여 답을 구해준다.

 

다리끼리는 서로 겹쳐질 수 없다고 하였는데 이것은 다리에 순서가 존재하지 않는다는 의미인 것 같다.

그래서 조합은 어차피 순서가 존재 하지않기 때문에 따로 다른 로직은 필요하지 않은것 같다.