[1254] 팰린드롬 만들기

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

1254번: 팰린드롬 만들기

<문제>

입력되는 문자열의 오른쪽에 0개 이상의 문자를 추가해, 팰린드롬을 만들어야 한다.

이때, 추가하는 문자의 최소값을 구하는 문제다.

입력되는 문자열을 s로 부르면,

팰린드롬을 만족하는 s의 부분문자열 [start, end]의 길이 len = end - start + 1이 길어질 수록 최적해에 가깝다.

길이 5의 s가 입력될때, 2번째~5번째 문자가 팰린드롬을 만족한다면

1번째 문자를 6번째 문자로 추가적으로 넣어서 [1, 6]이 팰린드롬을 만족하도록 구성할 수 있다.

 

또한, 추가하는 문자가 없다면(입력이 자체로 팰린드롬을 만족하는 경우)

s의 길이가 곧 최적해가 되고, 이것이 모든 경우에서의 최소값이 되므로

answer = n(입력되는 문자열 s의 길이) + i(팰린드롬을 만족하는 부분 문자열의 시작 인덱스)

i를 최소로 만들기 위해 구간 [i, end]가 팰린드롬이면 바로 조기종료하고, 정답을 출력하면 되겠다.

<소스코드>

#include<bits/stdc++.h>
using namespace std;
int n;
bool f(int start, string s) {
    string s1 = s;
    reverse(s.begin() + start, s.end());
    string s2 = s;
    if (s1 == s2)return true;
    return false;
}
int main(void) {
    string s;
    cin >> s;
    n = s.length();
    int i;
    for (i = 0; i < n; i++)
        if (f(i, s) == true)
            break;
    cout << i + n;
    return 0;
}