백준[1509] 팰린드롬 분할

문제 설명

문제 링크

http://icpc.me/1509

풀이

dp를 2번 사용하여 풀이할 수 있다.

palin[i][j] : 문자열 구간 i ~ j 까지가 팰린드롬인지 여부

s[i] == s[j] 이면서 i+1 ~ j-1이 팰린드롬이면 i ~ j 가 팰린드롬이다.

이렇게 구해둔 팰린드롬인지 여부를 이용하여 한번 더 dp를 돌린다.

dp[i] : 1 ~ i까지 최소 분할 팰린드롬 수

if palin[i][j] == true : dp[j] = max(dp[j], dp[i - 1] + 1)로 정의 할 수 있다.

코드

#include <iostream>
#include <string>

using namespace std;

bool palin[2503][2503];
int dp[2503];

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    string s; cin >> s;
    int n = s.size();
    s = " " + s;
    for (int i = 1; i <= n; i++) palin[i][i] = true;
    for (int i = 1; i < n; i++) palin[i][i + 1] = (s[i] == s[i + 1]);
    for (int j = 2; j < n; j++) {
        for (int i = 1; i + j <= n; i++) {
            if (s[i] == s[i + j] && palin[i + 1][i + j - 1]) palin[i][i + j] = 1;
        }
    }
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1e9;
        for (int j = 1; j <= i; j++) {
            if (palin[j][i]) dp[i] = min(dp[i], dp[j - 1] + 1);
        }
    }
    cout << dp[n];
}