[Baekjoon]백준 1010 다리놓기(실버 5) - Python

문제설명

예제

문제를 살펴보면 다리를 지을 수 있는 경우의 수를 출력해야한다

서로 다리가 겹치면 안 된다는 문제의 조건(중요)가 있기 때문에

그냥 고를 수 있는 경우의 수를 각각 곱하면 되는 것이 아니다

두 번째로 주어진 동쪽에 있는 사이트의 개수에서 M개를 안 겹치게 뽑아서 N개의 다리를 순서대로 놓으면 된다

그러면 다리가 서로 겹치지 않고 다리를 지을 수 있다

그 말인 즉슨, mCn을 구하여 출력하는 것이 이 문제의 핵심이다

 

이전에 풀이하였던 factorial 함수를 활용하여 코드를 작성하였다

def factorial(num):
    if num > 1:
        return num * factorial(num - 1)
    else:
        return 1
    
T = int(input())

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