Informatica Online Judge

  회문 [0350 / 015E]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 51   Total Tried : 35


The Champion of this Problem (C++) : gs15120 - 35ms / 1450byte
My Best Submission (C++) : N/A

[IOI 2000 - Beijing, China]

Background

회문(Palindrome) 이란 글자가 좌우 대칭을 이루고 있어서, 왼쪽부터 읽으나 오른쪽부터 읽으나 같은 의미가 되는 말을 일컫는다.

어떤 문자열이 있는데, 여기 아무 위치에 글자를 몇 자 더하여 이 문자열을 좌우 같은 말로 만들려고 한다. 어떠한 방법으로든지 최소한 몇 자를 더해야 이 문자열을 좌우 같은 말로 만들 수 있는지 계산하는 프로그램을 작성하라.

예를 들어 "Ab3bd"란 문자열은 글자 두 자를 적당한 곳에 끼워넣어서 "dAb3bAd", "Adb3bdA"와 같은 꼴의 회문으로 만들 수 있다. 하지만 두 자보다 글자를 적게 넣어서는 회문을 만들 수 없다.

Input

첫째 줄에는 문자열의 길이 N (3<=N<=5000) 이 들어있고, 둘째 줄에는 길이가 N인 문자열이 들어있다.

문자열에는 알파벳 대소문자와 숫자(0~9) 가 들어있으며, 대소문자를 구분한다.

Output

입력된 문자열을 회문으로 만들기 위해 더해야 하는 문자 개수의 최소값을, 첫째줄에 출력하면 된다.

IO Example

입력
5
Ab3bd

출력
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]