[C++] 백준 1010 - 다리 놓기

🔐 백준 1010 - 다리 놓기

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

🔑 풀이

서쪽과 동쪽의 사이트들을 잇는 경우의 수를 구하는 문제이다. 서쪽의 사이트 수 만큼 다리를

건설해야 하며, 다리를 겹칠 수 없다.

조합(Combination)을 구하는 문제로 동쪽의 M개의 사이트 중, 서쪽의 사이트 개수인 N개를 고르면

해결할 수 있는 문제이다. 고르는 순서는 고려할 필요가 없는데, 이유는 동쪽에서 N개의 사이트를 고를 경우

다리가 교차되면 안되기 때문에, N개의 사이트를 분배하는 순서는 하나만 존재하기 때문이다.

그렇다면 간단히 조합 공식인 $ C(M, N) = \frac{M!}{N!(M - N)!} $ 으로 해결할 수 있다.

long long combination(int n, int r) {
    if (r == 0 || r == n) {
        return 1;
    }
    return factorial(n) / (factorial(r) * factorial(n - r));
}

또 다른 방법으로는 DP로 문제를 해결할 수도 있다.

조합을 구하는 방법 중 다음과 같은 점화식을 사용할 수 있다.

$ C(n, k) = C(n-1, k-1) + C(n-1, k) $

n개의 요소 중 k개의 요소를 고르는 조합의 수는:

• n번째 요소를 선택하고, n-1개의 요소에서 k-1개를 고르는 경우 = C(n-1, k-1)

• n번째 요소를 선택하지 않고, n-1개의 요소에서 k개를 고르는 경우 = C(n-1, k)

로 나눌 수 있다.

🧩 코드