BOJ 1509 팰린드롬 분할

1 개요

BOJ 1509 팰린드롬 분할

• 백준 온라인 저지 1509번 문제
• BOJ 47단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.length();
    vector<int> dp(n + 1, 0);
    vector<vector<bool>> pal(n, vector<bool>(n, false));

    for (int i = 0; i < n; ++i) {
        pal[i][i] = true; // 한 글자는 항상 팰린드롬
        dp[i + 1] = i + 1; // 최악의 경우: 모든 문자를 개별적으로 분할
    }

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

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (pal[j][i - 1]) {
                dp[i] = min(dp[i], dp[j] + 1);
            }
        }
    }
    cout << dp[n];
}