[백준 1509] 팰린드롬 분할

 

 DP로 시작해서 DP로 끝나는 문제이다.

 

 먼저 팰린드롬 분할 조합 중 최솟값을 구하는 로직이 필요하다. 이는 문자열의 특정 위치에서의 팰린드롬 분할 개수의 최솟값을 저장할 DP 배열을 만들어 구할 수 있다. 일단 dp[i]은 dp[i-1]+1이 될 수 있다. 직전 문자열까지의 최솟값에 새로 더해지는 문자를 하나의 팰린드롬으로 보는 경우이다.

 하지만 문제에서 요구하는 것은 최솟값이므로, 앞서 등장한 문자열과 새로 더해지는 문자를 함께 이용해서 팰린드롬을 만들었을 때의 분할 개수가 더 적지는 않은지 확인해야만 한다. 그러니까 [i-1, i] 구간이 팰린드롬인지 확인하고, 팰린드롬이라면 dp[i-2]+1이 최소가 될 수 있는지 확인하고, 같은 방식으로 [i-2, i], [i-3, i], ..., [0, i] 까지 모두 확인해주어야 한다. 그러므로 DP 배열을 완성하는 로직의 시간 복잡도만 O(n^2)가 된다.

 이 때, 브루트 포스를 통해서 팰린드롬을 판정하려면 O(n)이 될 것이므로(문자열의 양 끝값부터 중앙으로 접근하며 하나씩 일치하는지 확인한다고 할 때), 총 시간복잡도는 O(n^3)에 달하기 때문에 제한 시간 내에 해결할 수 없다.

 

 그렇기 때문에, 전처리를 통해 특정 구간의 문자열이 팰린드롬인지 확인할 수 있는 2차원 배열을 따로 준비해두어야 한다(그렇게 되면 팰린드롬 판정의 시간복잡도는 O(1)이다).물론 팰린드롬을 위의 브루트 포스 방식으로 전처리한다면 O(n^3)만큼 걸리게 되므로 의미가 없고, 이 때도 DP를 활용할 수 있다.

 특정 문자열이 팰린드롬인지 확인할 때, 문자열의 길이가 1이라면 이는 팰린드롬이다. 그리고 길이가 2라면 두 값이 일치할 때만 팰린드롬이다. 이를 이용해서 DP에 필요한 초기 값을 세팅할 수 있다. 다음으로 길이가 3 이상일 때는, 양 끝 값이 일치하는지 확인하고, 일치한다면 DP 테이블을 이용해 양 끝값을 제외한 사이의 구간이 팰린드롬인지 확인해서 구해내면 된다. 이는 점화식의 형태이므로, 이제 DP를 적용하면 끝이다.

 나는 위의 로직을 바탕으로 팰린드롬 판별 함수를 구현했고, 길이가 1인 경우부터 문자열 전체 길이에 해당하는 경우까지 반복문을 통해 팰린드롬 DP 테이블을 완성했다. 이 때 시간복잡도는 길이를 1에서 n까지 늘려가면서 매번 문자열의 첫 인덱스부터 끝 인덱스까지 한번씩 적용하며 확인하므로 O(n^2)에 해당한다.

 

 전처리 하는 로직의 시간복잡도가 O(n^2), 분할 최소 개수를 구하는 로직의 시간복잡도가 O(n^2)이므로 전체 시간 복잡도는 O(n^2)의 복잡도로 이 문제를 해결할 수 있게 된다. 

#include <iostream>
#include <algorithm>

using namespace std;

bool palindromeMatrix[2500][2500] = {false, };
string s;

bool isPalindrome(int start, int end) {
    if(s[start]==s[end]) {
        if(end-start<2) return true;

        return palindromeMatrix[start+1][end-1];
    } else {
        return false;
    }
}

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

    for(int i=0; i<len; i++) {
        for(int j=0; j+i<len; j++) {
            palindromeMatrix[j][j+i] = isPalindrome(j, j+i);
        }
    }

    int dp[2501] = {0, };

    for(int i=0; i<len; i++) {
        dp[i+1] = dp[i]+1;
        for(int j=0; j<i; j++) {
            if(palindromeMatrix[j][i]==1) {
                dp[i+1] = min(dp[i+1], dp[j]+1);
            }
        }
    }

    cout << dp[len];
    
}