팰린드롬 분할

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

DP를 활용해서 쉽게 풀어줄 수 있다.

정확히는 (1)임의의 부분문자열이 회문인지를 위한 DP, (2)특정 위치까지의 문자열의 파티션 수를 헤아리기 위한 DP, 이렇게 총 2회의 DP가 필요로 된다.

(2)번부터 풀이를 기술하면, 아래와 같이 CACHE를 정의할 수 있다.

• CACHE[i]: i번째 문자까지 고려할 때(i.e. S[0:i+1]) 파티션의 갯수

점화식은 아래와 같이 세워줄 수 있다.

• CACHE[i] = min(CACHE[j] + 1) (단, S[j, i + 1]은 회문)

위의 점화식은 이전 단계에서 구해놓은 파티션에 새로운 회문 1개를 더해주는 것을 의미한다.

(2)번을 푸는 과정에서 임의의 연속 부분문자열이 회문인지의 여부를 반복적으로 확인하게 된다.

이를 위한 풀이 과정이 곧 (1)번이며, 아래와 같이 CACHE를 정의할 수 있다.

• CACHE[i][j]: S[i:j+1]이 회문인지의 여부

점화식은 아래와 같다.

• CACHE[i][j] = S[i] == S[j] && CACHE[i+1][j-1]

위의 점화식을 풀 때, 마치 현재의 답이 미래의 답에 의존하는 듯한 인상을 받을 수 있다.(i+1때문에)

하지만, 이는 단순히 루프의 순서를 조정해주는 것을 통해 쉽게 해결해줄 수 있다.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int kMaxN = 2500;

int N;
string S;
int PARTITIONS[kMaxN + 1];
int PALINDROME[kMaxN + 1][kMaxN + 1];

int main(void)
{
  // For faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read input
  cin >> S;
  N = (int)S.size();
  S = "-" + S;

  // Solve palindrome table
  for (int s = N; s >= 0; --s)
  {
    for (int e = s; e <= N; ++e)
    {
      if (s == e)
      {
        PALINDROME[s][e] = 1;
      }
      else if (S[s] == S[e] && (s + 1 > e - 1 || PALINDROME[s + 1][e - 1] == 1))
      {
        PALINDROME[s][e] = 1;
      }
      else
      {
        PALINDROME[s][e] = 0;
      }
    }
  }

  // Solve
  PARTITIONS[0] = 0;
  for (int pos = 1; pos <= N; ++pos)
  {
    PARTITIONS[pos] = kMaxN * kMaxN;
    for (int prev = pos - 1; prev >= 0; --prev)
    {
      if (PALINDROME[prev + 1][pos])
      {
        PARTITIONS[pos] = min(PARTITIONS[pos], PARTITIONS[prev] + 1);
      }
    }
  }

  cout << PARTITIONS[N] << '\n';

  return 0;
}