[BOJ 1509] 팰린드롬 분할

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

입력되어진 문자열을 팰린드롬들로 분할하였을 때 그 분할개수의 최소값을 출력하는 문제이다. 

최소값을 구하는 문제라고 적혀있는 것처럼 DP로 접근을 해보자. 

dp 배열의 개념을 먼저 잡고 가자면 dp[i] 는 문자열 i번째 문자까지 갔을 떄 필요한 최소한의 팰린드롬 개수이다. 

따라서 점화식을 새운다면 dp[i] = min(dp[j-1])+1  ( 여기서 i와 j는 팰린드롬 일 경우 )이 될 것이다. 

따라서 먼저 i와 j가 팰린드롬인지를 판별하는 함수를 먼저 만들고 점화식대로 문제를 해결해나가면 된다. 

#include <iostream>
#include <cstdio>
#include <cstring>
 
 
using namespace std;
 
int arr[2555][2555],dp[2555];
 
string s;
int len;
 
int get(int a,int b){
    if(a == b){
        return arr[a][b];
    }
    int &ret = arr[a][b];
    if(a+1 == b){
        if(s[a] == s[b]){
            return ret = 1;
        }else{
            return ret = 0;
        }
    }
    if(ret >=0){
        return ret;
    }if(s[a] != s[b]){
        return ret = 0;
    }else{
        return ret = get(a+1,b-1);
    }
}
int main(){
    memset(arr,-1,sizeof(arr));
    cin >>s;
    s = " " +s;
    len = s.length();
    
    for(int i=1;i<=len;i++){
        arr[i][i] = 1;
    }
    dp[0] = 0;
    for (int i=1; i<=len; i++) {
        dp[i] = -1;
        for (int j=1; j<=i; j++) {
            if (get(j,i) == 1) {
                if (dp[i] == -1 || dp[i] > dp[j-1]+1) {
                    dp[i] = dp[j-1]+1;
                }
            }
        }
    }
    printf("%d\n" , dp[len-1]);
    return 0;
 
}
 

이렇게 팰린드롬인지를 확인하고 점화식을 진행해 나가면 된다. 

팰린드롬을 판별하는 방법은 위와같이 재귀적으로도 채워나갈 수 있고 , for문으로도 가능하다. 

for (int i=1; i<=len-1; i++) {
    if (s[i] == s[i+1]) {
        arr[i][i+1] = true;
    }
}
for (int k=2; k<len; k++) {
    for (int i=1; i<=len-k; i++) {
        int j = i+k;
        arr[i][j] = (s[i] == s[j] && arr[i+1][j-1]);
    }
}