백준 #1254 팰린드롬 만들기

팰린드롬(Pallindrome)이라는 것은 앞에서 읽어도, 뒤에서 읽어도 같은 숫자나 단어가 되는 것을 말합니다.  예를 들어서 "a nut for a jar of tuna" 은 공백을 제거하면 팰린드롬이 되는 문귀가 됩니다.

 

Pallindrome

 

이번 문제는 주어진 단어에 대해서 적절하게 단어 뒤에 문자를 추가하여 팰린드롬이 되는 단어가 되도록 하는 것입니다.  이 때, 가장 짧은 팰린드로의 길이를 찾아내는 문제죠.  "abba" 와 같은 경우에는 자체로 팰린드롬이므로 4를 출력하면 됩니다.  "banana" 라면 b만 추가하면 "bananab"가 되어 팰린드롬이 되므로 7을 출력합니다.

 

난이도  Silver II에 정답률 40.6%의 평이한 문제입니다.

 

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

1254번: 팰린드롬 만들기

이 문제는 동적 프로그래밍을 사용하는 문제로 분류가 되어 있습니다.  하지만 동적 프로그래밍이 답일지는 모르겠네요.  가장 좋은 알고리즘은 맨 마지막 글자가 나타날때마다, 연속된 부분 문자열이 팰린드롬인지 검사하는 것입니다.  뭐 어차피 팰린드롬 검사할 때, 맨 마지막 글자와 부분문자열의 맨 처음 글자와 제일 먼저 비교할테니, 크게 상관이 없습니다.

 

제가 작성한 소스 코드입니다.  소스는 참고용으로 봐주세요.

//--------------------------------------------------------------------
//  baekjoon #1254 - Making Pallindrome
//    - by Aubrey Choi
//    - created at 2019-08-05
//--------------------------------------------------------------------
#include <stdio.h>
#include <string.h>

bool check(char str[], int s, int n)
{
  for(s++,n-=2;s<n;) if(str[s++]!=str[n--]) return false;
  return true;
}

int main()
{
  char s[1004];
  gets(s);
  int len=strlen(s), i;
  for(i=0;i<len-1;i++)
  {
    if(s[i]!=s[len-1]) continue;
    if(check(s, i, len)) break;
  }
  printf("%d\n", len+i);
}