#1509 팰린드롬 분할

팰린드롬 분할은 주어진 문자열에 팰린드롬이 되는 단어들로 나눌 때 나오는 팰린드롬의 개수가 최소가 되는 수를 계산합니다.

 

맞힌 사람들의 수행시간을 보니, 제 알고리즘은 그다지 좋지는 않습니다.  제 알고리즘은 \(O(N^3)\)인데, 이보다 적게 계산할 수 있는 방법이 있겠죠.

 

일단 기본적인 생각은 앞에서부터 n개의 글자에 대한 팰린드롬 분할의 최소 개수를 구합니다.  이것을 \(dp_n\)이라고 한다면,

 

1개의 글자는 그 자체로 팰린드롬이니,

\[ dp_0 = 0, dp_1 = 1 \]

이 됩니다.

 

\[ dp_{n+1} = min_{i = 0,...,n-1}(dp_{i} + 1~ if~ s[i:n]~is~pallindrome) \]

 

이 방식대로 구현한 프로그램은 아래와 같습니다.  좀 더 효율적인 프로그램을 생각해볼만한데, 좋은 아이디어가 떠오르지는 않네요.

//----------------------------------------------------------
//    baekjoon #1509 - Pallidndrome Partition
//        - by Aubrey Choi
//        - created at 2020-01-26
//----------------------------------------------------------
#include <stdio.h>

int main()
{
    static int dp[2501]; int n, i, j, min;
    char s[2504];
    scanf("%s",s);
    for(n=1,dp[1]=1;s[n];n++)
    {
        min=dp[n]+1;
        for(i=0;i<n;i++)
        {
            if(s[i]!=s[n]) continue;
            for(j=1;i+j*2<n;j++) if(s[i+j]!=s[n-j]) break;
            if(i+j*2>=n) min=(min>dp[i]+1)?dp[i]+1:min;
        }
        dp[n+1]=min;
    }
    printf("%d\n", dp[n]);
}