[C++] 팰린드롬 분할 (백준 1509번)

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

 

dp 배열 2개를 사용해서 풀었다.

1. 모든 구간에 대해서 팰린드롬인지 아닌지를 저장하는 배열

p[i][j] : i부터 j까지의 문자열이 팰린드롬이면 true, 아니면 false

이 배열을 채울 때는 구간의 길이가 1일 때, 2일 때, ... 순서로 채워준다. 어떤 구간이 팰린드롬이고 직전 문자와 직후 문자가 같으면 그 구간도 팰린드롬임을 활용해서 채우면 된다.

2. 팰린드롬 분할 개수의 최솟값을 저장하는 배열 (정답을 구하는 배열)

dp[i] : i까지의 문자열의 팰린드롬 분할 개수의 최솟값

이 배열은 0부터 j까지의 팰린드롬 분할 개수의 최솟값, 즉 dp[j]가 x이고 j+1부터 i까지의 문자열이 팰린드롬이면 dp[i]를 x + 1로 갱신할 수 있다는 것을 이용해서 채우면 된다. 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string s;
    cin >> s;
    int n = s.size();

    vector<vector<bool>> p(n, vector<bool>(n, false));
    vector<int> dp(n, 10000);

    for (int i = 0; i < n; i++) p[i][i] = true;
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) p[i][i + 1] = true;
    }
    for (int i = 2; i < n; i++) {
        for (int j = 0; j + i < n; j++) {
            if (p[j + 1][j + i - 1] && s[j] == s[j + i]) p[j][j + i] = true;
        }
    }

    for (int i = 0; i < n; i++) {
        if (p[0][i]) {
            dp[i] = 1;
        } else {
            for (int k = 0; k < i; k++) {
                if (p[i - k][i]) dp[i] = min(dp[i], dp[i - k - 1] + 1);
            }
        }
    }

    cout << dp[n - 1] << '\n';
}

(AC)