백준 1509번 팰린드롬 분할[C++]

1. 문제 풀이

 동적계획법(dynamic_programming)을 사용하여 풀이하였습니다. 부분 문자열이 palindrome임을 확인하는 dp와 분할 개수의 최솟값을 구하는 dp로 두 번 나누어 진행하여 풀이하였습니다. 부분 문자열이 palindrome 확인 로직은 중앙값을 잡고 상태 유지 여부를 확인하면서 갱신하였습니다. 이때, palindrome의 길이가 짝수인 경우는 중앙값이 두 개 필요하므로 홀수, 짝수를 나누어서 갱신했습니다. 분할 개수를 확인하는 로직은 0, n-1 사이에 mid값을 counter로 문자열[0 : mid+1]이 palindrome이면 [mid+1 : en]에서 palindrome을 찾게 재귀로 구현하여 풀이했습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n; // |str|
string str;
bool ispalindrome[2501][2501];
int d[2501][2501];

int solve(int st, int en){
  if(d[st][en] != -1) return d[st][en];
  if(ispalindrome[st][en]) return d[st][en] = 1;

  int ans = 3000;
  for(int mid = st; mid < en; mid++){
    if(ispalindrome[st][mid]) ans = min(ans, 1 + solve(mid+1, en));
  }
  return d[st][en] = ans;
}

int main() {
  fastio(nullptr, false);

  // input
  cin >> str;

  // init
  n = sz(str); // n is |str|
  ispalindrome[0][0] = 1;
  ispalindrome[n-1][n-1] = 1;
  if(str[0] == str[1]) ispalindrome[0][1] = 1;
  if(str[n-1] == str[n-2]) ispalindrome[n-2][n-1] = 1;
  
  // solve
  for(int i = 1; i < n-1; i++){
    ispalindrome[i][i] = 1; // 자기자신은 항상 palindrome

    int st = i - 1;
    int en = i + 1;
    while(st >= 0 && en < n && str[st] == str[en] && ispalindrome[st+1][en-1]) ispalindrome[st--][en++] = 1;
    if(str[i] == str[i+1]){
      ispalindrome[i][i+1] = 1;
      st = i - 1;
      en = i + 2;
      while(st >= 0 && en < n && str[st] == str[en] && ispalindrome[st+1][en-1]) ispalindrome[st--][en++] = 1;
    }
  }

  // output
  memset(d, -1, sizeof(d)); 
  cout << solve(0, n-1);
}

 

3. 제출 결과