[C++] BAEKJOON 1509 팰린드롬 분할

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

1509번: 팰린드롬 분할

 

지난 포스팅에서는 팰린드롬인지 아닌지 판별하는 문제를 동적계획법을 이용해서 해결해보았습니다.

팰린드롬?

[C++] BAEKJOON 10942 팰린드롬?

이번 문제는 이를 응용하여 해결할 수 있습니다. 동적계획법을 통해 dp[i]][j] (=i번째부터 j번째 까지의 문자열이 팰린드롬인지) 를 정의하고 이를 통해 문제를 해결합니다. count[i] ( i 번째 까지 문자열에 대해 팰린드롬 분할의 개수의 최솟값) 에 값을 저장합니다. i 를 기준으로 j 를 1부터 i 까지 순회하며 j~i 의 문자열이 팰린드롬을 이룬다면 이것으로 자르는게 최소 분할이 될지를 검사해줍니다. 그러기 위해 count 배열에는 큰 수로 초기화 시켜놨습니다.

#include <iostream>
#include <string>

using namespace std;

bool dp[2501][2501];

int main() {
    
    int count[2501];
    
    string s;
    cin >> s;
    int n = s.size();
    s = " " + s;
    
    for (int i=1; i<=n; i++) {
        dp[i][i] = true;
    }
    for (int i=1; i<=n-1; i++) {
        if (s[i] == s[i+1]) {
            dp[i][i+1] = true;
        }
    }
    for (int k=2; k<n; k++) {
        for (int i=1; i<=n-k; i++) {
            int j = i+k;
            if (s[i] == s[j] && dp[i+1][j-1]){
                dp[i][j] = 1;
            }
        }
    }
    count[0] = 0;
    for (int i=1; i<=n; i++) {
        count[i] = 987654321;
        for (int j=1; j<=i; j++) {
            if (dp[j][i]) {
                if (count[i] > count[j-1]+1) {
                    count[i] = count[j-1]+1;
                }
            }
        }
    }

    cout << count[n] << '\n';
    return 0;
}