[백준 1509] 팰린드롬 분할

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

무려 DP를 2번이나 구현해야하는 문제이다.

풀이 과정

1. 팰린드롬 구하기
   palindrome[i][j] = palindrome[i + 1][j - 1];
   • 문자열의 범위(0~len)일때 ,구하려는 범위의 시작을 i, 끝을 j로 두자
   • 범위가 1일때: 무조건 true
   • 범위가 2일때: 두글자가 모두 같으면 true
   • 범위가 3이상 일때:양끝 글자가 같고, 그 속 글자들이 모두 같을때 (ㅁOOOOㅁ)
     양 끝 안의 값이 같은지 어떻게 알지? -> i+1~j-1까지가 성립하는지 확인하면 됨
2. 최소 분할 개수 구하기
   ans[j] = min(ans[j], ans[i-1] + 1)
   • 0~i까지의 범위 중 ture인 값을 구하기
   • 0~i까지 ture라면? 쪼개진게 없으므로 1
   • j~i까지 ture라면? j까지 쪼개진거 + 1 (j+1~i까지 새롭게 쪼개짐)
3. len-1의 최소 분할 개수 출력

구현

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

using namespace std;

int main() {
    
    string s;
    cin >> s;
    int l = s.length();
    bool palindrome[2501][2501] = {false};
    for (int i = 0; i < l; i++) { // 1개일때 모두 트루
        palindrome[i][i] = true;  
    }

    for (int j = 1; j < l; j++) {
        for (int i = 0; i < j; i++) {
            if (s[i] == s[j]) {
                if (j - i == 1) {
                    palindrome[i][j] = true; // 2개일때(aa) 
                } else {
                    palindrome[i][j] = palindrome[i + 1][j - 1]; //OㅁㅁㅁㅁㅁO
                }
            }
        }
    }

    vector<int> ans(l, INT_MAX);  // 0부터 n까지의 최소 분할 개수 저장
    for (int j = 0; j < l; j++) {
        if (palindrome[0][j]) ans[j] = 1;  // 0~j까지가 true면 1로 끝.
        else {
            for (int i = 1; i <= j; i++) {
                if (palindrome[i][j]) ans[j] = min(ans[j], ans[i-1] + 1); // 분할됐으므로 +1
            }
        }
    }
    
    cout << ans[l - 1]; 

    return 0;
}

참고
https://byeo.tistory.com/entry/boj-1509-%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC-%EB%B6%84%ED%95%A0