문제

문제 링크

문제 접근

  • 이 문제는 처음부터 각 수를 기준으로 해서 팰린드롬을 만들고 각 위치까지 올 수 있는 최소 개수를 업데이트한다.

코드

#include <cstdio>
char s[2501];
int i, dp[2501], x, y, pre;
int main(){
    scanf("%s", s);
    for(int i = 0; i < 2501; i++)dp[i] = 2500;
    for(i = 0; s[i] != '\0'; i++){
        x = y = i;
        while(x >= 0 && s[x] == s[y]){
            if(x - 1 >= 0)pre = dp[x - 1];
            else pre = 0;
            if(pre + 1 < dp[y])dp[y] = pre + 1;
            x--, y++;
        }

        x = i - 1, y = i;
        while(x >= 0 && s[x] == s[y]){
            if(x - 1 >= 0)pre = dp[x - 1];
            else pre = 0;
            if(pre + 1 < dp[y])dp[y] = pre + 1;
            x--, y++;
        }
    }
    printf("%d", dp[i - 1]);
}

느낀점

  • 팰린드롬은 다 비슷한 것 같다!