[BOJ] 1509 - 팰린드롬 분할

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

BOJ - 팰린드롬 분할

문제 유형: 팰린드롬, 문자열 처리, 다이나믹 프로그래밍

문제 난이도: Gold I

시간 제한: 2초

메모리 제한: 128MB

 

문제

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.

분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 문자열이 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있고, 최대 길이는 2,500이다.

 

출력

첫째 줄에 팰린드롬 분할의 개수의 최솟값을 출력한다.

 

풀이

isPalindrome[l][r] = [l, r]구간에 대해 팰린드롬인지에 대한 여부를 저장한 2D 불리언 배열을 만든다.

가운데에서 넓히면서 팰린드롬을 확인하는 방식으로 구한다. 홀수 케이스와 짝수 케이스 모두 해준다.

 

그 뒤, dp[i] = i길이의 prefix를 구성하는 최소 팰린드롬수로 한다.

dp[0] = 0이다.

각각의 i에 대해서, 우선, dp[i] = dp[i-1] + 1이다. 한 글자짜리 팰린드롬을 추가하는 경우이다. 만약 1 <= j < i에 대해, [j-1][i-1]이 팰린드롬이라면, dp[i]는 dp[j-1]+1이 될 수 있다. 만약 이것이 수를 더 줄여준다면, 이것으로 한다.

 

최종적으로 dp[n]에 정답이 들어있다. 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

string s;
bool isPalindrome[2501][2501];

int main(int argc, char *argv[]) {
  cin >> s;
  int n = s.size();
  if (n == 0) {
    cout << "0\n";
    return 0;
  }

  for (int i = 0; i < n; ++i) {
    isPalindrome[i][i] = true;
    int l = i - 1;
    int r = i + 1;
    while (l >= 0 && r < n && s[l] == s[r]) {
      isPalindrome[l][r] = true;
      l--;
      r++;
    }

    l = i;
    r = i + 1;
    while (l >= 0 && r < n && s[l] == s[r]) {
      isPalindrome[l][r] = true;
      l--;
      r++;
    }
  }

  vector<int> dp(n + 1, INT_MAX);
  dp[0] = 0;
  for (int i = 1; i <= n; ++i) {
    dp[i] = dp[i - 1] + 1;
    for (int j = 1; j < i; ++j) {
      if (isPalindrome[j - 1][i - 1])
        dp[i] = min(dp[i], dp[j - 1] + 1);
    }
  }

  cout << dp[n] << "\n";

  return 0;
}