백준 1010 - 다리놓기

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

1010번: 다리 놓기

단순하게 조합을 사용하면 풀리는 문제

근데 왜 조합을 사용하는 건지 모르겠어서 문제를 못풀었었다.

순서를 생각하지 않고 r개를 택할 경우 조합을 사용한다.

ex) 동쪽에 3개의 다리  A, B, C가 있고 서쪽에 2개의 다리 D, E가 있다고 하자. 

서로 다리를 이으려면 서쪽에 있는 다리의 갯수만큼 동쪽에 있는 다리들 중에서 고르면 된다.

 

==> 그럼 문제는  A, B, C 중에서 2개를 택하는 문제로 바뀐다.

선택해보자

 A, B /  A, C /  B, C 이렇게 3가지 경우가 나온다

 B, A / C, A / C, B를 택해도 위와 동일하므로 고려하지 않는다.

그냥 골라서 겹치지 않게 연결해주면 됨

 

만약, 겹쳐도 된다고 하면 순서를 고려하게 되는 것이므로 조합이 아닌 순열 P를 사용하면 된다.

 

조합을 푸는 문제는 앞선 포스팅에서 모듈을 임포트하여 구했으므로 이번에는 직접 함수를 구현하여 문제를 풀어봤다.

 

def fac(a):
    result =1
    for i in range(1, a+1):
        result*=i
    return result


T = int(input())
for i in range(T):
    N, M =map(int, input().split())
    print(fac(M)//fac(N)//fac(M-N))