BOJ 2647 검은점과 하얀점

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

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

 

처음에 그리디로 한 네 번쯤 삽질하다가 다 예제에 막히고 포기했습니다. 태그 까고 나서 DP인걸 알고도 하루 종일 고민했는데 안 풀려서 cologne 님께 풀이를 들었습니다.

 

$dp[l][r]$을 $l$부터 $r$까지의 구간에서 매칭했을 때의 최솟값으로 두면 됩니다. 역추적도 필요한데, 메모이제이션을 할 때 $l$이 어느 점과 이어졌는지를 기록하면 역추적을 할 수 있습니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()

const int INF = 0x3f3f3f3f;

using namespace std;

int T, n, memo[110][110], height[110][110], matching[110][110];
vector<int> vec;
vector<pii> ans;

int dp(int l, int r) {
  if (l > r) return 0;
  if (memo[l][r]) return memo[l][r];

  int ret = INF;
  int h = 0;
  int m = -1;

  for (int i = l + 1; i <= r; i += 2) {
    if (vec[i] == vec[l]) continue;

    int tmp = 0;

    tmp += dp(l + 1, i - 1);
    tmp += (height[l + 1][i - 1] + 1) * 2 + (i - l);

    tmp += dp(i + 1, r);

    if (tmp < ret) {
      ret = tmp;
      h = max(height[l + 1][i - 1] + 1, height[i + 1][r]);
      m = i;
    }
  }

  height[l][r] = h;
  matching[l][r] = m;
  return memo[l][r] = ret;
}

void check(int l, int r) {
  if (l + 1 > r) return;

  int m = matching[l][r];
  ans.push_back({ l, m });
  check(l + 1, m - 1);
  check(m + 1, r);
}

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> n;

    vec.resize(n);
    for (int i = 0; i < n; i++) {
      char c;
      cin >> c;
      if (c == '1') vec[i]++;
    }

    cout << dp(0, n - 1) << endl;

    check(0, n - 1);
    sort(all(ans));

    for (auto [a, b] : ans) cout << a + 1 << ends << b + 1 << endl;
  }

  return 0;
}