[BOJ] 1509: 팰린드롬 분할 (C/C++)

문제 1509번: 팰린드롬 분할

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

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

입력

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

출력

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

문제분석

문제 요구사항

• 문자열 내 Palindrome을 찾아야함
• 문자열 을 Palindrome으로 분할하여 분할의 최솟값을 찾아야함

효과적으로 분할의 최솟값을 찾기위하여 Dynamic Programming을 활용하여 분할 최솟값 탐색

구현

먼저 문자열의 [left, right]범위의 부분 문자열이 Palindrome임을 저장하는 is_palindrome vector를 선언 한 후, [left, right]부분 문자열이 Palindrome일시 true를 저장 함, 그 후 Dynamic Programming을 활용하여 dp[index] 에[0,index]구간의 분할 최솟값을 저장하는 dp vector를 선언하여 dp.back()을 통하여 문자열의 분할 최솟값을 구함.

증명

dp[index]의 분할 최솟값을 구하는 경우 dp[0]-dp[index-1]까지 모두 분할 최솟값이 들어 있다고 가정한다.
문자열의 길이가 1인 경우, 해당 문자열은 Palindrome으로 처리된다. 따라서 dp[index-1] + 1의 연산의 경우, 이때 집합 $\boldsymbol{\forall n \in N, N=\{1, 2, 3, … n\}의\;dp[n-1] + right - n + 1}$을 내포하고 있기에, 범위 [left, index]의 부분 문자열이 Palindrome인 경우만 비교를 하여도 dp[index]의 분할 최솟값을 찾을 수 있다.

코드

#include <iostream>
#include <string>
#include <vector>

const size_t ConvertToIndex(const int left, const int right) {
  return left + (right * (right + 1) >> 1);
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);

  std::string s;
  s.reserve(2500);
  std::cin >> s;

  std::vector<bool> is_palindrom((s.length() + 1) * s.length() >> 1, false);
  for (int i = 0; i < 2 * s.length() - 1; ++i) {
    int left = i >> 1, right = (i + 1) >> 1;
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
      is_palindrom[ConvertToIndex(left--, right++)] = true;
    }
  }

  std::vector<int> dp(s.length());
  for (int right = 0; right < dp.size(); ++right) {
    if (is_palindrom[ConvertToIndex(0, right)]) {
      dp[right] = 1;
      continue;
    }
    dp[right] = right + 1;
    for (int left = right; left >= 1; --left) {
      if (is_palindrom[ConvertToIndex(left, right)]) {
        dp[right] = std::min(dp[right], dp[left - 1] + 1);
      }
    }
  }

  std::cout << dp.back();

  return 0;
}