백준 문제 1509번 팰린드롬 분할 문제풀이 c++

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

1509번: 팰린드롬 분할

문제해석

 

예전에 못 풀어서 넘겼던 문제인데 10942번 팰린드롬? 문제를 풀고 나니 풀 수가 있게 되었다.

 

일단 저번글에서 작성했던 팰린드롬?의 코드를 최대 2500글자이니까 그 부분만 수정하고 코드 그대로 가져와서 활용했다.

 

총 dp를 두번 사용하였다.

 

처음 dp는 dp로 팰린드롬?문제와 동일한 i~j번째 문자열이 팰린드롬인가를 판단하는 2차원 dp 배열이다.

이는 단순 dp로 배열을 채워나갔다.

 

두번째 dp는 ans 1차원 배열로 ans[i]를 i번째 문자부터 끝 문자까지 팰린드롬 분할을 최소로 했을때 갯수로 정의하였다.

깊이 우선 탐색을 활용한 dp로 ans배열을 채워나갔다.

 

우리가 구하고자하는 것은 첫번째 문자부터 끝 문자까지 팰린드롬 분할을 최소로 하는 것이기 때문에 ans[1]을 구해야한다.

 

최소로 분할 하는 값을 찾아야하므로 ans 배열을 채울때 뒤에서 부터 채워가야한다. 

2500글자 문자열이라면 ans[2500]을 채운후에 ans[2499] ans[2498] ...... ans[1] 

그런식으로 작성한 코드는 다음과같다.

 

코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
void dfs(int start);
char a[2505];
bool dp[2505][2505];
int ans[2505];
int n;
int cnt=0;
int mn=9999;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    string str;
    cin>>str;
    n=str.size();
    for(int i=1; i<=n; i++)
    {
        a[i]=str[i-1];
    }
    for(int i=1; i<=2500; i++)
    {
        dp[i][i]=1;
        if(a[i]==a[i+1])
        {
            dp[i][i+1]=1;
        }
    }
    for(int j=2498; j>=1; j--)
    {
        for(int i=1; i<=j; i++)
        {
            if((dp[i+1][i+2500-j-1]==1)&&(a[i]==a[i+2500-j]))
            {
                dp[i][i+2500-j]=1;
            }
        }
    }
    for(int i=n; i>=1; i--)
    {
        dfs(i);
        ans[i]=mn;
        cnt=0;
        mn=9999;
    }
    cout<<ans[1];
}
void dfs(int start){
    if(start>n)
    {
        mn=min(cnt,mn);
        return;
    }
    if(ans[start])
    {
        mn=min(mn,cnt+ans[start]);
        return;
    }
    else
    {
        for(int i=start; i<=n; i++)
        {
            if(dp[start][i]==1)
            {
                cnt++;
                dfs(i+1);
                cnt--;
            }
        }
    }
}