1509. 팰린드롬 분할

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

1509번: 팰린드롬 분할

 

문제 설명

어떤 문자열이 주어집니다.

팰린드롬 단위로 문자열을 분할했을 때, 분할의 수가 가장 적은 값을 출력하면 되는 문제입니다.

 

풀이

분할 수를 가장 적게 하려면 팰린드롬 단위로 자를 때 가장 큰 단위로 잘라야합니다.

문자열 "AAAA"를 {A, A, A, A}, {AA, AA}, {AAA, A} .... 으로 나눌 수 있지만 {AAAA} 가 가장 최소입니다.

 

이 문제를 두가지 부분문제로 나눌 수 있습니다.

1. 팰린드롬인지 아닌지 확인하는 문제. (팰린드롬 판별)

2. 분할의 수가 가장 적은 값을 도출하는 문제.

 

 

먼저 팰린드롬 판별 부분입니다.

2차원 DP 테이블에 메모이제이션을 하면서 해결할 수 있는데, 첫번째 인덱스는 start, 두번째 인덱스는 end를 뜻하게 합니다.

그렇게 양쪽에서 중간지점까지 팰린드롬인지 아닌지를 저장하며 움직이면 됩니다.

 

int dp[2505][2505];
int checkPal(int starti, int endi)
{
    int& ret = dp[starti][endi];
    if(ret != -1) return ret;
    if(starti >= endi) return 1;
    if(s[starti] != s[endi]) return ret = 0;
    return ret = checkPal(starti+1, endi-1);
}

 

 

다음은 분할의 수가 가장 적은 값을 도출하는 부분입니다.

이 부분도 DP를 활용해서 해결할 수 있습니다.

 

현재 위치에서 이 문자가 추가되는 것이 팰린드롬이 아닐 경우 dp[i] = dp[i-1] + 1 이 됩니다.

그리고 1번부터 현재위치까지 팰린드롬인지 확인하여 dp 테이블을 갱신합니다.

 

이렇게 해결하면 총 시간복잡도는 O(N^2) 이 됩니다.

문자열의 길이가 최대 2500 이므로 충분히 가능합니다.

 

 

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
int dp[2505][2505];
int table[2505];
string s;
int n;
 
int checkPal(int starti, int endi)
{
    int& ret = dp[starti][endi];
    if(ret != -1) return ret;
    if(starti >= endi) return 1;
    if(s[starti] != s[endi]) return ret = 0;
    return ret = checkPal(starti+1, endi-1);
}
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> s;
    n = s.length();
    s = " " + s;
 
    memset(dp, -1, sizeof(dp));
    memset(table, INT_MAX, sizeof(table));
 
    table[0] = 0;
    for(int i=1;i<=n;i++)
    {
        table[i] = table[i-1] + 1;
        for(int j=1;j<i;j++)
        {
            if(!checkPal(j, i)) continue;
            table[i] = min(table[i], table[j-1]+1);
        }
    }
    cout << table[n];
    return 0;
}