1254 팰린드롬 만들기

백준 1254 팰린드롬 만들기 https://www.acmicpc.net/problem/1254

주어진 문자열에서 0개이상의 문자를 추가해서 가장 짧은 팰린드롬의 길이를 구하는 문제이다.
이게 DP문제인지 질문에서도 논란이 되는데 나는 잘 모르겠다.(DP로는 안품)

길이가 L인 문자열 내부에 가장 긴 팰린드롬을 찾았을 3가지 경우에 대해 생각해 보겠다.

1. 왼쪽

먼저 문자열중 앞쪽이 팰린드롬일 경우이다. 여기서 뒤에 얼만큼의 문자열을 추가해야 팰린드롬이 될까? 팰린드롬 될 요소가 없으므로 L-1개의 문자열을 추가해야 L번째 문자를 대칭으로 팰린드롬이 될것이다.


 2. 중앙

중앙에 있는 경우를 생각해 보자. 이 경우도 따져보면 L-1개의 문자열을 추가해야 L번째 문자를 대칭으로 팰린드롬이 된다.

3. 오른쪽

마지막으로 왼쪽에 있는 경우이다. N번에서 L번까지의 문자열이 팰린드롬일 경우에는 1번에서 N번까지의 문자열을 대칭시켜 뒤에 붙이면 팰린드롬이 만들어지기 때문에 N개의 문자열만 추가하면 된다.

즉 세가지의 경우를 따질 필요도없이 끝을 기준으로 어디까지가 팰린드롬인지만 찾아서 N을 더해주면 된다. 해당 팰린드롬이 없는 나머지경우는 모두 L-1개의 문자열을 추가한 2*L - 1의 길이가 되겠다.

#include <cstdio> char str[1001]; bool pal(int f, int s){     int l = s - f + 1;     int cnt = l / 2;     if (cnt == 0)         return false;     for (int n = 0; n < cnt; n++){         if (str[f + n] != str[s - n])             return false;            // not palindrome     }     return true; } int main(){     int l;     scanf("%s", str);     for (l = 0; str[l]; l++);     if (l == 1){         printf("1\n");         return 0;     }     for (int n = 0; n < l; n++){         if (pal(n, l - 1)){             printf("%d\n", l + n);             return 0;         }     }     printf("%d\n", l + l - 1);     return 0; } O(n*n)알고리즘인데 Manacher Algorithm으로는 O(n)에 해결 가능하다고 한다. Cㅇlored  by Color Scripter

cs