백준 1010 - 다리놓기[조합]

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

1010번: 다리 놓기

 

 

 

from itertools  import combinations

n,m=map(int,input().split())
arr=list(range(1,n+1))

arr2=list(combinations(arr,m))

print(len(arr2))

 

위와 같은 코드로 조합의 경우의 수를 셀수도 있지만 해당 문제는 0.5초라는 시간 제한이 이기 때문에 다른 접근 법이 필요하다.

 

 

 

 

def factorial(n):
    num = 1
    for i in range(1, n+1):
        num *= i
    return num


T = int(input())

for _ in range(T):
    n, m = map(int, input().split())
    bridge = factorial(m) // (factorial(n) * factorial(m - n))
    print(bridge)

 

m이 n보다 크기 때문에 최대 연결할 수 있는 다리의 개수는 n개이고 m개의 지역에 n개의 다리를 놓을 수 있는 경우의 수를 구하는 것이기 때문에  mCn 으로 표현할 수 있고 이는 m! 을 (m-n)!n! 으로 나눈 값이다.