[1254번] 팰린드롬 만들기

문제 출처 :

https://www.acmicpc.net/problem/1254

알고리즘 분석 :

문제 해결에 필요한 사항

1. 팰린드롬 :: http://www.crocus.co.kr/1001?category=209527

이 문제는 위의 링크를 통해 알고리즘을 이해하고 접목하면 쉽다.

예를들어보자.

acwdbbd라면 dbbd는 팰린드롬이니 acwdbbdwca만 더 추가된다면 가장 최소 팰린드롬을 만들 수 있다.

따라서 i~문자열 마지막까지의 최대 팰린드롬을 구한다면(여기선 dbbd)

(전체 길이 - 최대 팰린드롬 길이) * 2 + 최대 팰린드롬 길이가 정답이 된다. 

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#include <iostream> #include <cstdio> #include <string.h> #include <algorithm>   using namespace std;   char str[1002]; bool DP[1002][1002];   int main() {     scanf("%s", str + 1);     int len = strlen(str + 1);     for (int i = 1; i <= len; i++)         DP[i][i] = true;       for (int i = 1; i <= len - 1; i++)         if (str[i] == str[i + 1])             DP[i][i + 1] = true;       // k칸 다음번째     for (int k = 2; k <= len - 1; k++)     {         // 1부터 ~ n - k 번째 까지         for (int i = 1; i <= len - k; i++)         {             // i + k번째 칸             int j = i + k;             if (str[i] == str[j] && DP[i + 1][j - 1])                 DP[i][j] = true;         }     }       int val = -1;     for (int i = 1; i <= len; i++)         if (DP[i][len])             val = max(val, len - i + 1);       printf("%d", val + (len - val) * 2);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus