BAEKJOON 1509번: 팰린드롬 분할

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

1509번: 팰린드롬 분할

풀이

일단 간단하게 생각할 수 있는 점화식을 정의해 보자

 

D[i]는 문자열 S의 i번째 까지 고려했을 때 분할의 개수의 최솟값.

자연스럽게, if(S[i]~S[j]가 팰린드롬) D[i]=D[j-1]+1 이 성립함을 알 수 있다.

 

이제 매번 S[i~j]가 팰린드롬임을 어떻게 확인하냐는 건데, Manacher를 이용해도 좋지만 너무 오버킬인 감이 있다.

 

"g[i][j]는 문자열 S의 i~j까지의 부분문자열이 팰린드롬이면 1 아니면 -1" 이라고 하자.

i≤j 라는 조건 하에, g[i][j] = (S[i]==S[j] and g[i+1][j-1]==1)?(1):(-1) 이다.

물론, i=j 이거나, i=j+1, i=j+2일 경우, g[i][j]=1 이 항상 성립하므로 따로 생각해주자.

 

이제 이를 필요한 부분만 재귀적으로 구하되, 이미 구해 두었다면 g[i][j]를 이용하도록 하자.

 

소스코드

위의 풀이를 보고도 이해가 전혀 되지 않는다면 참고합시다.

#include <bits/stdc++.h>
using namespace std;
int D[2503],g[2503][2503];
char S[2503];
int G(int i,int j){
    if(i>j)return g[i][j]=-1;
    if(g[i][j])return g[i][j];
    if(j-i<=2)return g[i][j]=(S[i]==S[j]?1:-1);
    return g[i][j]=(S[i]==S[j]&&G(i+1,j-1)==1)?1:-1;
}
int main(){
    scanf("%s",S);
    int n=strlen(S);
    for(int i=0;i<n;i++){
        D[i]=D[i-1]+1;
        if(G(0,i)==1)D[i]=1;
        for(int j=1;j<i;j++){
            if(G(j,i)==1)D[i]=min(D[i],D[j-1]+1);
        }
    }
    printf("%d",D[n-1]);
    return 0;
}