[BOJ] 백준 1010 다리 놓기

문제 링크

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

다음과 같은 그림에서 서쪽 사이트의 개수만큼 다리를 지으려 할 때 겹치지 않게 다리를 모두 지을 수 있는 경우의 수를 구해야 한다.

다리끼리는 서로 겹쳐질 수 없다라는 조건이 있다.

이런 경우는 가능하지만

이런 경우는 불가능하다는 것이다.

서쪽 사이트의 집합을 $A$, 동쪽 사이트의 집합을 $B$라 하면 

$1 \leq i, j \leq N$ 인 $i,\,j$와

$1 \leq x, y \leq M$ 인 $x,\,y$에 대해 

$A[i]$와 $B[x],\,A[j]$와 $B[y]$가 연결된다면 항상 $i<j$이고 $x<y$여야 한다.

쉽게 말하면 서쪽의 두 정점과 동쪽의 두 정점이 연결된다면 항상 순서대로 연결되어야 한다는 말이다.

확장해서, 서쪽과 동쪽에서 각각 정확히 $N$개의 정점을 선택할 때 양쪽의 정점은 항상 순서대로 연결되게 된다.

서쪽의 정점 $N$개는 모두 선택되어야 하고, 동쪽의 사이트 $M$개 중에서 어떤 $N$개의 정점을 선택했을 때 다리를 지을 수 있는 방법의 수는 항상 1이다.

따라서 우리는 이 문제를 $M$개 중 $N$개를 고르는 경우의 수를 구하는 문제로 단순화할 수 있다.

이는 결국 조합 $_mC_n$ 이 몇인가를 묻는 문제이다.

정답 코드