IOI 2000 day1 1- 회문(Palindrome) > 문제은행 : 정보올림피아드&알고리즘




1449 : 회문(Palindrome)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
21 회   
시도횟수
184 회   

문제

palindrome(팰린드롬:회문)이란 글자가 좌우 대칭을 이루고 있어서, 

왼쪽부터 읽으나 오른쪽부터 읽으나 같은 의미가 되는 말을 일컫는다. 

어떤 문자열이 있을 때, 임의의 위치에 0개 이상의 글자를 더하여 이 문자열을 좌우 같은 말로 만들려고 한다. 

방법이야 어떻든 최소한 몇 자를 더해야 이 문자열을 palindrome(팰린드롬:회문)으로 만들 수 있는지 계산하는 프로그램을 작성하시오.

 

예를 들어 "Ab3bd"란 문자열은 글자 두 자를 적당한 곳에 끼워넣어서

"dAb3bAd", "Adb3bdA"와 같은 꼴로 palindrome(팰린드롬:회문)을 만들 수 있다. 

 

하지만 두 글자보다 적게 넣어서는 palindrome(팰린드롬:회문)을 만들 수 없다. 


입력형식

첫 행에 문자열의 길이 N(3 <= N <= 5000)이 주어진다. 둘째 행에 길이가 N인 문자열이 주어진다. 문자열에는 알파벳 대소문자와 숫자(0~9)로 이루어져 있으며 대소문자는 구분한다.

출력형식

첫 행에 palindrome(팰린드롬:회문)을 만들기 위해 추가해야 하는 문자 개수의 최소값을 출력한다.

입력 예

5
Ab3bd

출력 예

2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP