(1509) 팰린드롬 분할

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

단계별로 풀어보기

50단계(동적 계획법 4) 1번째

 

 

 

pal[i][j]를 입력된 문자열의 i~j번째 글자가 팰린드롬을 이루는지 여부를 나타내는 불리언 변수라고 하자.

pal[i][j]는 i번째 글자와 j번째 글자가 같고, j-i≤1(같은 글자거나 바로 옆)이거나 pal[i+1][j-1]이 true일 때 true다.

이 방식으로 O(N^2)에 pal을 전처리할 수 있다.

 

dp[i]를 i번째 글자까지 팰린드롬 분할 가능한 최소값이라고 하자.

pal[x][i]가 true일 때 x~i번째 글자가 하나의 팰린드롬이고 1~x-1번째 글자를 다시 분할해야 하므로 dp[i]= max(dp[i], dp[x-1]+1)이 된다. 이 비교를 x가 1~i일 때에 대해 하면 dp[i]를 구할 수 있다. 시간복잡도는 O(N^2)이다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  string s;
  
  cin >> s;
  
  int len= s.length();
  
  vector<int> dp(len+1);
  vector pal(len+1, vector<bool> (len+1));
  
  for(int i=0;i<len;i++){
    for(int j=1;j+i<=len;j++){
      pal[j][j+i]= (s[j-1]==s[j+i-1] && (i<=1||pal[j+1][j+i-1]));
    }
  }
  
  for(int i=1;i<=len;i++){
    dp[i]= i;
    
    for(int j=1;j<=i;j++){
      if(pal[j][i])  dp[i]= min(dp[i], dp[j-1]+1);
    }
  }
  
  cout << dp[len];
  
  return 0;
}