[백준 1509] 팰린드롬 분할 C++

1509번: 팰린드롬 분할

다이나믹 프로그래밍

---

1. 문제 해결 아이디어

 

anaban의 dptable

 

일단 문자열의 모든 범위에 따른 팰린드롬 여부를 2차원 table로 만들었다.

dp[st][ed]에는 st부터 ed까지의 문자열이 팰린드롬인지 확인여부가 담겨있다.

 

dp table을 채울 때 str[st]와 str[ed]가 같고 dp[st+1][ed-1]이 팰린드롬이면 dp[st][ed]도 팰린드롬인 성질을 이용해서 O(n^2)으로 테이블을 구할 수 있다.

 

dp 테이블을 구했으니 최소 팰린드롬 분할 수를 구해보자

 

res배열을 만들었다.

res[2]는 2번째 문자열 까지 탐색했을 때 최소 팰린드롬 분할 수를 저장하고 있다는 뜻이다.

 

따라서 2차원 for문을 통해서 res의 최솟값을 갱신해 나간다면 res[N]이 답이 될 것이다!

 

---

2. 코드

 

#include <iostream> 
#include <cstring>
 
#define INF 1e9+7
 
using namespace std;
 
bool dp[2501][2501];
string str;
int N, res[2501];
 
bool is_palin(int st, int ed){
    if(ed > N) return false;
    
    if(str[st] == str[ed]){
        if(dp[st+1][ed-1] || ed-st == 1){
            return true;
        }
    }
    return false;
}
 
void fill_dptable(){
    for(int d = 0; d < N; d++){
        for(int i = 1; i+d <= N; i++){
            if(d == 0){
                dp[i][i] = true;
                continue;
            }
            if(is_palin(i, i+d)){
                dp[i][i+d] = true;
            }
        }
    }
}
 
void solve(){
    fill_dptable();
    
    res[0] = 0;
    for (int i = 1; i <= N; i++) {
        res[i] = INF;
        for (int j = 1; j <= i; j++) {
            if (dp[j][i]) {
                if (res[i] > res[j-1]+1) {
                    res[i] = res[j-1]+1;
                }
            }
        }
    }
    cout << res[N];
}
 
int main(){
    cin >> str;
    N = str.size();
    str = " " + str;
    solve();
    
    return 0;
}