[Python] 백준 1010. 다리놓기

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

1010번: 다리 놓기

 

문제설명: 

강 서쪽, 동쪽으로 N, M 사이트가 주어졌을때 다리를 놓을 수 있는 경우의 수를 구하는 문제이다.

만약 N이 6 M이 8일때 생각해야 될 경우

둘이 엇갈리게 놓을 수 없다. 다리가 서로 가로 지를 수 없다.

한 사이트에서는 하나의 다리만 놓을 수 있다.

 

결국, 사이트를 선택하는 방법은 M개 중에 N개를 선택해야 한다. 서로 중복되면 안된다. => 조합 방식이다.

 

조합의 공식을 보면 n개 중 r개를 뽑는다. 즉, 8C6으로 생각하면 된다. 8개중에 6개를 선택한다.

교차되는 것은 조합에서 어떻게 구분하는지 상관없다. 조합은 순서 상관없다 만약 12345 중에 321을 뽑는것과 123을 뽑는 것을 같은 것으로 보고 있다.

 

cnt = int(input())

def combin(num):
    result = 1
    for i in range(1,num+1):
        result *= i
    return result
for case in range(cnt):
    n,m = map(int, input().split())
    
    # 조합의 공식이 사용되었다.
    answer = combin(m) // (combin(m-n) * combin(n))
    print(answer)