[백준] 1509번: 팰린드롬 분할

📌 문제

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

📌 설명

처음부터 끝까지 문자열을 순회하면서 팰린드롬을 찾고, 계속하여 최솟값을 갱신해야 한다.

dp[i]를 i번 째 문자까지의 최소 분할 횟수라고 하자. 현재, 문자열의 i번 째 인덱스를 가리킨다고 할 때, i번 째 문자를 마지막으로 하는 팰린드롬이 있는지 확인한다. 만약 문자열 처음부터 팰린드롬이라면 최소 분할 횟수 minCuts를 1로 설정한다. 만약 j번 째 문자부터 i번 째 문자까지 팰린드롬이라면 분할 횟수는 dp[j - 1] + 1이다. 물론 이 경우가 최적이 아닐 수 있기 때문에 minCuts과 dp[j - 1] + 1 중 작은 값을 취해야 할 것이다.

📌 코드

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

using namespace std;

string s;
int dp[2501]; // dp[i]: i번 째까지 분할된 팰린드롬의 최솟값

bool isPalindrome(int start, int end) {
    while (start < end) {
        if (s[start] != s[end]) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

int main() {
    cin >> s;
    
    int n = s.length();

    for (int i = 0; i < n; i++) {
        int minCuts = i + 1; // 최대 i + 1번 분할 가능
        for (int j = 0; j <= i; j++) {
            if (isPalindrome(j, i)) {
                // j부터 i까지 하나의 팰린드롬임. 이때 i까지 최소 팰린드롬의 수는 dp[j - 1] + 1이 될 수 있음.
                // 만약 처음부터 하나의 팰린드롬이라면 1로 간주
                minCuts = (j == 0) ? 1 : min(minCuts, dp[j - 1] + 1);
            }
        }
        dp[i] = minCuts;
    }

    cout << dp[n - 1];
}