[백준 1254번] 팰린드롬 만들기 (C++)

문제링크 : https://www.acmicpc.net/problem/1254

1254번: 팰린드롬 만들기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

bool check(string tmp) //펠린드롬인지 아닌지 확인
{
    for(int i=0; i<tmp.size()/2; i++)
    {
        if(tmp[i]!=tmp[tmp.size()-1-i]) return false; //아님
    }
    return true; //맞음
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    string s;
    int result = 1; //최소 팰린드롬은 1
    cin >> s;
    for(int i=0; i<s.size(); i++)
    {
        if(check(s.substr(i))) result = max(result, (int)s.size()-i); //제일 큰 펠린드롬 확인
    }

    cout << int(s.size() + int(s.size()-result));
    return 0;
}

현재 문자열을 하나씩 줄여가면서 최소 팰린드롬을 확인해준다.

문자열 내에 가능한 팰린드롬 중에서 가장 큰 값을 저장하고 해당 값을 기준으로 좌우를 복사해준다.

 

s.size()-i를 사용하여 팰린드롬 수를 저장해줄 때 int(s.size())를 해주어야 한다.

이는 s.size()가 long unsigned int의 범위를 가지기 때문에 뒤에 -i를 해주는 과정에서 오류가 발생한다.

이를 방지하기 위해서 s.size() 앞에 int로 명시적 형변환을 취해준다.

 

이후에는 전체 문자열의 길이에서 팰린드롬 수를 제외한 문자만큼이 반복되므로,

전체 문자열에 길이에 추가적으로 전체에서 팰린드롬 문자열 만큼 빼준값을 더해주면 된다.