[BOJ 2647] 검은점과 하얀점 연결

문제

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

2647번: 검은점과 하얀점 연결

 

---

알고리즘

• DP

---

풀이

DP 역추적 문제입니다.

점들에 대한 정보가 주어졌을 때, 다음 \(3\)개의 배열을 만들어 정의할 수 있습니다:

 

• \(dp[i][j]:\) \(i\)번째부터 \(j\)번째까지의 점으로 길을 만들 때, 길의 거리의 합의 최솟값.
• \(hgt[i][j]:\) \(i\)번째부터 \(j\)번째까지의 점으로 길을 만들 때, 높이가 가장 높은 길의 높이(올라간 거리).
• \(last[i][j]:\) \(i\)번째부터 \(j\)번째까지의 점으로 길을 만들 때, 길을 나누는 방법(아래 추가 설명).

점들을 이어 여러 개의 길을 만들 수 있는데, 어떻게 있느냐가 중요합니다.

길을 나누는 방법은 다음 두 가지로 나누어 생각할 수 있습니다:

 

• 길 하나를 감싸는 경우 - \((i, j), (i + 1, j - 1)\)
• 두 부분으로 나누는 경우 - \((i, k), (k + 1, j)\)

그러므로, 점화식을 다음과 같이 세울 수 있습니다:

 

$$dp[i][j] = \min \begin{cases}
dp[i + 1][j - 1] + 2 \cdot (hgt[i + 1][j + 1] + 1) + j - i\\
\min_{i < k < j} dp[i][k] + dp[k + 1][j],& \text{where}\ (k - i) \text{ mod } 2 = 1
\end{cases}$$

 

\(hgt[i][j]\)는 위의 두 값중 첫 번째 값이 더 작은 경우, \(hgt[i + 1][j - 1] + 1\), 두 번째 값이 더 작은 경우, \(\max(hgt[i][k], hgt[k + 1][j])\)가 됩니다.

\(last[i][j]\)는 첫 번째 값이 더 작은 경우, \(-1\), 두 번째 값이 더 작은 경우, \(k\)를 넣어 역추적을 할 수 있도록 합니다.

 

길의 거리의 합을 구해 출력한 다음, 역추적을 진행합니다:

 

1. \(last[i][j]\)의 값을 토대로 \(-1\)이면 \((i + 1, j - 1)\), \(k\)이면 \((i, k), (k + 1, j)\)의 구간을 봅니다.
2. 더이상 나눌 수 없거나, 길을 감싸는 경우에는 포함하는 길이 \(1\)개이므로 \((i, j)\)를 출력하면 됩니다.

시간복잡도: \(O(N^3)\)

 

---

코드

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N, dp[101][101], hgt[101][101], last[101][101];
string S;

int dfs(int s, int e) {
    if (s == e - 1) {
        if (S[s] == S[e]) return 100000;
        hgt[s][e] = 1;
        return dp[s][e] = 3;
    }
    if (dp[s][e]) return dp[s][e];

    int ans = 1e9, comp;
    for (int i = s + 1; i < e - 1; i += 2) {
        comp = dfs(s, i) + dfs(i + 1, e);
        if (ans > comp) {
            ans = comp;
            hgt[s][e] = max(hgt[s][i], hgt[i + 1][e]);
            last[s][e] = i;
        }
    }

    if (S[s] != S[e] && s + 1 < e - 1) {
        comp = dfs(s + 1, e - 1) + (hgt[s + 1][e - 1] + 1) * 2 + e - s;
        if (ans > comp) {
            ans = comp;
            hgt[s][e] = hgt[s + 1][e - 1] + 1;
            last[s][e] = -1;
        }
    }

    return dp[s][e] = ans;
}

void traceback(int s, int e) {
    if (s >= e) return;
    if (s == e - 1) {
        cout << s << ' ' << e << '\n';
        return;
    }
    if (last[s][e] == -1) {
        cout << s << ' ' << e << '\n';
        traceback(s + 1, e - 1);
    }
    else {
        traceback(s, last[s][e]);
        traceback(last[s][e] + 1, e);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> S;
    S.insert(S.begin(), '.');
    cout << dfs(1, N) << '\n';
    traceback(1, N);

    return 0;
}