(백준 c++)1509 팰린드롬 분할

문제

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.

분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열이 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있고, 최대 길이는 2,500이다.

출력

첫째 줄에 팰린드롬 분할의 개수의 최솟값을 출력한다.

 

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(void){
    string s;
    vector<vector<int>> dp(2501, vector<int>(2501, 0));
    vector<int> count(2501, 0);
    int size = 0;

    cin >> s;
    s.insert(0, " ");
    
    size = s.size();

    //dp를 통한 회문 검사
    //1글자 회문
    for(int i = 1; i < size; i++){
        dp[i][i] = 1;
    }

    //2글자 회문
    for(int i = 1; i < size; i++){
        if(s[i] == s[i + 1]){
            dp[i][i + 1] = 1;
        }
    }

    //3글자 이상 회문
    for(int i = 2; i < size; i++){
        for(int j = 1; j <= size - i; j++){
            if(s[j] == s[i + j] && dp[j + 1][i + j - 1]){
                dp[j][i + j] = 1;
            }
        }
    }

    //최소 분할 개수 구하기
    for(int i = 1; i < size; i++){
        count[i] = 999999999;
        for(int j = 1; j <= i; j++){
            if(dp[j][i]){
                count[i] = count[i] < count[j - 1] + 1 ? count[i] : count[j - 1] + 1;
            }
        }
    }
 
	cout << count[size - 1];
    return 0;
}