[BOJ] 백준 1509 팰린드롬 분할

문제 링크

www.acmicpc.net/problem/1509

1509번: 팰린드롬 분할

 

풀이

입력받은 문자열의 $i$번부터 끝까지 해당되는 부분 문자열을 s라 합시다.

$d[i]$: $s$를 팰린드롬 분할했을 때 분할 개수의 최솟값.

 

각 문자열을 두 구간으로 나눠봅니다.

$i$부터 시작하는 문자열 s에서 $u = (i$ ~ $j)$, $v = (j+1$ ~ $)$ 이렇게 두 구간으로 나눴을 때

$u$가 팰린드롬이면 $d[u] = 1 + d[v]$입니다.

 

어떤 문자열이 팰린드롬인지는 백준 10942 팰린드롬? 문제와 같은 방식으로 판별할 수 있습니다.

각 부분 문자열을 나눌 수 있는 모든 두 구간으로 나누어 $d$의 최솟값을 구하면 됩니다.

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
using namespace std;

int n, d[2555], pal[2555][2555];
string s;

bool isPal(int i, int j) {
    if (i == j)return true;
    if (i + 1 == j) return s[i] == s[j];

    int &ret = pal[i][j];
    if (ret != -1) return ret;
    return ret = s[i] == s[j] && isPal(i + 1, j - 1);
}

int go(int i) {
    if (i == n) return 0;

    int &ret = d[i];
    if (ret != -1) return ret;
    ret = INF;
    for (int j = i; j < n; j++) {
        if (isPal(i, j)) {
            ret = min(ret, 1 + go(j + 1));
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(pal, -1, sizeof(pal));
    memset(d, -1, sizeof(d));
    cin >> s;
    n = s.size();
    cout << go(0);
}