BOJ 1010 - 다리 놓기 문제풀이

문제를 읽고 이해하기

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

 

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라. N, M (0 < N ≤ M < 30)

 

재정의와 추상화

사실 수학적으로만 생각한다면 매우 빠르게 끝낼 수 있는 문제이다. 동쪽이 항상 서쪽보다 원소가 많고, 서쪽의 도시가 동쪽의 도시에 대응되는 방식이 '겹치지 않게'라는 것을 보아, 대응 방식이 하나이다. 이 때, 동쪽의 도시 M개 중 서쪽의 도시 N개를 조합의 수로 선택해주기만 하면 답이 나온다.

 

즉, 답은 C(M, N) = C(M - 1, N) + C(M - 1, N - 1) 이다.

 

이렇게 수학적으로 먼저 생각했어야 했는데, 문제를 곧이곧대로 받아들이는 바람에 이상한 방법으로 알고리즘을 짰다.

아래는 내가 처음 '이상하게' 짠 알고리즘이다.

 

---

서쪽의 첫 번째 도시는 동쪽의 마지막 3개를 제외한 모든 도시를 선택할 수 있다. 그 이유는 마지막 3개를 남겨두지 않을 경우 서쪽의 나머지 3개의 도시는 갈 곳이 없기 때문이다.

 

그래서 서쪽의 첫 번째 도시가 갈 수 있는 범위는 0 ~ M - (N - 1) - 현재 도시 번호(0부터 시작)까지다. 다음 재귀호출을 할 때는 서쪽의 첫 번째 도시가 선택한 동쪽의 도시의 인덱스를 전달해주고, 그 인덱스를 이용하여 서쪽의 두 번쨰 도시가 갈 수 있는 범위를 동쪽의 도시의 인덱스 + 1 ~ M - (N - 1) - 현재 도시 번호까지로 한다.

 

이렇게 반복하다가 서쪽의 모든 도시가 동쪽의 도시와 짝지어졌을 경우 호출을 종료한다.

---

 

코드 작성

// 이상하게 짠 코드...

#include <iostream>
using namespace std;
 
int arr[30][30];
int ct = 0;
 
int dp(int count, int n, int m, int start) {
    // 기저
    if (count == n) return 1;
 
    // 메모이제이션 확인
    int &ref = arr[count][m - start];
    if (ref > 0)
        return ref;
 
    // 계산
    int sum = 0;
    for (int i = start; i < m - (n - 1 - count); i++)
        sum += dp(count + 1, n, m, i + 1);
 
    ref = sum;
    return ref;
}
 
int main() {
    int t, n, m;
    cin >> t;
 
    while (t--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
            for (int k = 0; k <= m; k++)
                arr[i][k] = 0;
        }
        cout << dp(0, n, m, 0) << '\n';
    }
    return 0;
}

// 이게 원래..

#include <iostream>
using namespace std;
 
int cache[30][30] = { 0, };
 
int dp(int n, int r) {
    // 기저
    if (r == 0 || n == r) // C(n, r) = 1 (n == r or r == 0)이라는 성질 이용
        return 1;
    // 메모이제이션 확인
    int& ref = cache[n][r];
    if (ref > 0)
        return ref;
    // x -> 계산
    ref = dp(n - 1, r) + dp(n - 1, r - 1);
    return ref;
}
 
int main() {
    int t;
    int n, m;
    cin >> t;
 
    while (t--) {
        cin >> n >> m;
        cout << dp(m, n) << '\n';
    }
    return 0;
}

 

회고하기

항상 DP 문제를 풀 때마다 수학적으로 생각하지 않고 무턱대고 문제를 곧이곧대로 받아들여 엉뚱한 방향으로 가는 경우가 많다. 이 부분은 종만북에서 얘기하는 재정의와 추상화 과정을 충실히 이행하지 않은 것으로 보인다. 앞으로 DP 문제를 많이 풀어나가면서 개선해나가자.