[BOJ 1254] 팰린드롬 만들기

이 문제는 다이나믹 프로그래밍으로 꼭 풀어야 하는건 아니다.

 

 

 

문자열의 i ~ j 구간의 팰린드롬 여부를 파악하도록 DP를 구성했다.

 

 

 

문자열의 끝에 0개 이상의 문자를 붙여서, 팰린드롬이 이루어지는지 볼려면, 모든 구간을 보는 것이 아니라,

 

 

 

0 <= i < S.length()

 

 

 

i에서부터 S.length() - 1까지 문자열이 팰린드롬인지 확인해서 붙어야 하는 문자 수를 파악하면 된다.

 

 

 

이 외의 구간들에 대해서는 팰린드롬인지 확인하는 것은 불필요하다.

 

 

 

해설코드(C++).

 

#include <iostream>
using namespace std;
 
string S;
int dp[1001][1001];
int main() {
    cin >> S;
    
    for(int i = 0; i < S.length(); i++){
        dp[i][i] = 1;
    }
    
    for(int i = 0; i < S.length() - 1; i++){
        if(S[i] == S[i + 1])
            dp[i][i + 1] = 1;
    }
        
    for(int k = 2; k < S.length(); k++){
        for(int i = 0; i < S.length(); i++){
            if(dp[i + 1][i + k - 1] == 1 && S[i] == S[i + k])
                dp[i][i + k] = 1;
        }
    }
    
    int answer = -1;
    for(int i = 0; i < S.length(); i++){
        if(dp[i][S.length() - 1] == 1){
            answer = max(answer, (int)S.length() - i);
        }
    }
    
    cout << answer + (S.length() - answer) * 2 << endl;
    return 0;
}