[BOJ 1695] 팰린드롬 만들기

[BOJ 1695] 팰린드롬 만들기

이 문제도 약 5시간정도 고민해서 풀었다. 이 문제를 풀면서 느낀 점은, dp유형의 문제는 현재상태와 이전상태가 어떤 관계를 통해서 서로 연결될 수 있는지를 규명하는게 중요하다는 점이다. 팰린드롬의 경우 단순히 dp[a][b]=dp[a][c]+dp[c][b]가 성립할 수 없는게 팰린드롬인 두 수열 '121'과 '232'를 서로 붙인 '121232'는 팰린드롬이 아니기 때문이다. 그래서 dp를 활용하기 위해서는 이전상태를 어떻게 이용할까를 고민하고 디자인하는게 중요하다. 그래서 문제에 등장하는 '특징'이 무엇일까를 잘 찾아내야 한다. 즉 문제에서 팰린드롬의 '특징'을 dp와 결부시켜야 하는 것이다. 그 특징이란 팰린드롬에서 dp[a][b]=dp[a+1][b-1]과 밀접한 연관이 있다는 것이다. '12321'이라는 문자열이 팰린드롬인지를 알아내기 위해서 인덱스 2~4번째인 '232'의 팰린드롬 여부가 중요하다. 그리고 이는 또 다시 3번째 인덱스인 '3'의 팰린드롬 여부가 중요하다. 이처럼 팰린드롬의 경우 밖에서 안으로 양 끝에 감싸고있는 문자(숫자)를 하나씩 짝 지을 수 있다는 것이 큰 특징이다. 이 문제는 팰린드롬이 활용된 것이고, 다른 소재들도 무궁무진하게 많다.

#include<stdio.h>
#include<algorithm>
using namespace std;
#define SIZE 5009
int arr[SIZE];
int dp[SIZE][SIZE];
int main(){
    int    n;    scanf("%d",&n);
 
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
    }
 
    for(int i=1 ; i<=n ; i++){
        if(arr[i]==arr[i+1])
            dp[i][i+2]=0;
        else dp[i][i+2]=1;
    }
 
    for(int i=3 ; i<=n ; i++){
        for(int j=1 ; j+i<=n+1 ; j++){
            int &ret=dp[j][j+i];
 
            int add;
            if(arr[j]==arr[j+i-1])
                add=0;
            else add=2;
 
            ret=min(dp[j+1][j+i-1]+add,min(dp[j+1][j+i]+1,dp[j][j+i-1]+1));        
        }
    }
    printf("%d\n",dp[1][n+1]);
 
    return 0;
}