[1254번] 팰린드롬 만들기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

팰린드롬인지 확인하는 O(n^2) 코드는 다음 링크에서 확인이 가능하다.

http://www.crocus.co.kr/1001

이제 위의 코드를 이용하여 문제를 해결해보자.

DP[i][j]의 의미는 i~j까지 부분 문자열이 팰린드롬인지 아닌지 기록하는 dp이다.

따라서 우리는 k~마지막번째까지의 dp[k][last]가 true인 최초 부분을 찾아준다.

예를들면 abcac가 있다고 보자

이때 팰린드롬 dp[3][5]가 처음으로 true가 될 것이다.(cac)

따라서 우리는 3~5번째는 고려하지 않고, 1,2번째만 현재 문자열 뒤에 추가해주면

이 문자열이 팰린드롬이 될 수 있음을 알 수 있다.(abcacba)

소스 코드 : 

#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 >>