BOJ 2135 - 문자열 압축하기

BOJ 2135 - 문자열 압축하기

$O(n^3)$ DP로 풀 수 있다.

$dp[l][r]$ 을 $l \sim r$ 문자열에서 최소 길이라고 하자.

transition은

• $l \sim r$ 구간을 두 부분으로 쪼개는 것
• $l$부터 시작하는 반복되는 문자열로 묶는 것

두 가지를 검사해주면 된다.

string s;
int n, dp[201][201];
string sub[201][201];

int fn(int l, int r) {
   if (l == r) return 1;
   if (l > r) return 0;
   int &ret = dp[l][r];
   if (~ret) return ret;
   ret = r - l + 1;

   for (int i = l; i <= r - 1; i++) {
      mina(ret, fn(l, i) + fn(i + 1, r));
   }

   for (int len = 1; len * 2 <= r - l + 1; len++) {
      int same = 1;
      for (int c = l + len; c + len - 1 <= r; c += len) {
         if (sub[l][l + len - 1] == sub[c][c + len - 1]) same++;
         else break;
      }
      if (same > 1) {
         mina(ret, sz(to_string(same)) + 2 + fn(l, l + len - 1) + fn(l + len * same, r));
      }
   }

   return ret;
}

void solve() {
   memset(dp, -1, sizeof dp);
   cin >> s;
   n = sz(s);
   for (int i = 0; i < n; i++) for (int j = i; j < n; j++) sub[i][j] = s.substr(i, j - i + 1);
   cout << fn(0, n - 1);
}