[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$ 이 몇인가를 묻는 문제이다.

정답 코드

	#include <iostream>
	#include <cstring>
	using namespace std;
	int t;
	int d[31][31];
	int foo(int n, int r) {
	if (n == r || r == 0)
	return 1;
	if (d[n][r]) return d[n][r];
	return d[n][r] = foo(n - 1, r - 1) + foo(n - 1, r);
	}
	int main() {
	cin >> t;
	while (t--) {
	memset(d, 0, sizeof(d));
	int n, m;
	cin >> n >> m;
	cout << foo(m, n) << '\n';
	}
	}

view raw 1010.cpp hosted with ❤ by GitHub