[boj : 1254] 팰린드롬 만들기

www.acmicpc.net/problem/1254

1254번: 팰린드롬 만들기

문제 : 팰린드롬 만들기까지 문자열 뒤에 몇개를 붙여 만들 수 있는가?

 

해설 : 팰린드롬 진짜 너무 싫네요 ㅠㅠㅠ 한번 꼬이면 반례가 안보여.....ㅠㅠ

먼저 필자는 팰린드롬이 무조건 '홀수'여야 된다고 잘못 생각했음.(멍청한 자식)

짝수도 되죠,,,,

 

맨 마지막 문자를 기준으로 모든 경우의 수를 확인해 보는 방식으로 풀었습니다.

1 - 0(L)번 인덱스와 맨 마지막 문자(R)

2 - 1번 인덱스와 맨 마지막 문자

3 - 2번 인덱스와 맨 마지막 문자

.

.

.

같다면 L과 R을 한칸씩 좁혀주고 전부 같으면 시작점(L)과 끝점(R)은 팰린드롬이라는 뜻이므로, 추가할 문자(L 값)을 더해주면 되겠죠.

 

#include<bits/stdc++.h>

using namespace std;
int solve(string& s, int x);
int main()
{
	string s;
	cin >> s;

	int ans = (int)1e9;
	for (int i = 0; i < s.length(); i++)
		if (solve(s, i)) {
			ans = i;
			break;
		}
	cout << ans + s.length();
	return 0;
}
int solve(string& s, int x)
{
	int l = x;
	int r = s.length() - 1;

	while (l < r)
	{
		if (s[l] != s[r])return false;
		l++;
		r--;
	}
	return true;
}