1509번

1509번 - 팰린드롬 분할

이 문제는 생각이 좀 부족해서 다른 설명을 보고 풀었다.

일단 점화식은

D[i]=i번 문자열까지 팰린드롬 분할했을 때, 최소갯수

솔직히 이 점화식까지는 생각했지만, 이를 어떻게 활용할지는 생각이 나지 않았다.

근데 여기서 점화식에는 포함되지 않는 변수 j 를 문자열 중간에 삽입하면 모든 퍼즐이 완성된다.

즉, 변수 j번 문자열부터 i번 문자열까지는 팰린드롬 수라고 가정한다면,

D[i] = min(D[i],D[j-1]+1) 이라는 식을 세울 수 있게된다. 뒤에서부터 짤라가는 과정이라고 생각하면 된다.

1. 뒤에서 부터 만들 수 있는 가장 긴 팰린드롬을 만든다.

2. 그 팰린드롬을 잘라낸 앞 부분에서 다시 위의 과정을 시작한다. 

j의 범위는 0부터 i 까지 나타낼 수 있다. 

예를 들어 ABCDCBA 라는 문자열이 있다고 하면, j=0 일때는 ABCDCBA 라는 전체가 되고 , j=i 일때는 맨 끝의 A 하나만 나타내게 된다.

이를 통해서 문제를 풀었다.

추가적으로 팰린드롬인지 확인하는 go 함수는 이전 문제(10942번)에서 DP를 이용해서 s~e까지 팰린드롬을 확인하는 방법을 이용해서

2500 x 2500 을 전부다 실행해서 팰린드롬이면 1이 나오도록 해놨다.

<정답 코드>

#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
 
int P[2501][2501];
int D[2501];
string str;
 
int go(int s,int e)
{
    if (s > e)
    {
        return 1;
    }
    
    if (P[s][e] >= 0)
    {
        return P[s][e];
    }
 
    if (str[s] == str[e])
    {
        P[s][e] = go(s + 1, e - 1);
    }
    else
    {
        return 0;
    }
 
    return P[s][e];
}
int go2(int N)
{
    if (N < 0)
    {
        return 0;
    }
    if (N == 0)
    {
        return 1;
    }
    if (D[N] > 0)
    {
        return D[N];
    }
 
    for (int i = 0; i <= N; i++)
    {
        if (P[i][N] == 1)
        {    
            if (D[N] == 0)
            {
                D[N] = go2(i-1) + 1;
            }
            else
            {
                D[N] = min(D[N],go2(i-1) + 1);
            }
        }
    }
 
    return D[N];
 
 
 
}
int main()
{
    
    cin >> str;
    int N = str.size();
    memset(P, -1, sizeof(P));
    memset(D, 0, sizeof(D));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            go(i, j);
        }
    }
 
    cout << go2(N-1) << endl;
 
    return 0;
}