취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1254번 문제인 팰린드롬 만들기이다.
문제는 아래 링크를 확인하자.

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

임의의 회문 문자열에 대하여, 그 문자열의 맨 앞글자와 뒷글자를 하나씩 제거해도 그 문자열은 다시 회문이 된다는 점을 관찰하자.

위의 성질을 이용하면, 주어진 문자열의 가장 긴 회문 접미사를 찾아, 해당 접미사를 중심으로 하는 회문을 새로 만들면 규완이가 원하는 문자열을 얻을 수 있다. 이렇게 만든 새 문자열의 길이는 원래의 문자열에서 회문 접미사의 길이를 뺀 만큼 길어진 값이 된다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

string s;

bool isPal(int L, int R) {
	while (L < R) {
		if (s[L] != s[R]) return 0;
		L++, R--;
	}
	return 1;
}

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

	cin >> s;
	int slen = s.length();
	for (int i = 0; i < slen; i++) {
		if (isPal(i, slen - 1)) {
			cout << slen + i;
			return 0;
		}
	}
}