시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 550 244 184 50.829%

문제

팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이 되게 되는 문자의 개수를 구하는 프로그램을 작성하여라.

예제에서는, 2개의 문자를 삽입하여 팰린드롬이 된다. "Ab3bd"는 "dAb3bAd" 혹은 "Adb3bdA" 로 바뀔 수 있다. 하지만, 2개 미만의 문자를 삽입해서는 팰린드롬이 될 수 없다.

입력

첫 번째 줄에는 문자열의 길이 N (3<=N<=5000)이 주어진다. 두 번째 줄에는 길이가 N인 문자열이 주어진다. 문자열은 대문자 'A'~'Z'와 소문자 'a'~'z', 숫자 0~9로 이루어진다. 대문자와 소문자는 구분되어야 한다.

출력

첫 번째 줄에 삽입해야할 최소 개수를 출력한다.

예제 입력 1

5
Ab3bd

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjU1MDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1Yjc4MCBcdWIzMDBcdWNlNmQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LiZuYnNwO1x1Yzk4OSwgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWM3N2RcdWM1YzhcdWM3NDRcdWI1NGNcdWM2NDAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwXHVjMTFjIFx1YzY3Y1x1Y2FiZFx1YzczY1x1Yjg1YyBcdWM3N2RcdWM1YzhcdWM3NDRcdWI1NGMgXHVhYzE5XHViMmU0XHViMjk0IFx1YzU5OFx1YWUzMFx1YjJlNC4gXHViMmY5XHVjMmUwXHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDRcdWI1NGMsIFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWM3NTggXHViYjM4XHVjNzkwXHViOTdjJm5ic3A7XHVjMGJkXHVjNzg1XHVkNTU4XHVjNWVjIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWI0MThcdWFjOGMgXHViNDE4XHViMjk0IFx1YmIzOFx1Yzc5MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCwgMlx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjMGJkXHVjNzg1XHVkNTU4XHVjNWVjIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWI0MWNcdWIyZTQuICZxdW90O0FiM2JkJnF1b3Q7XHViMjk0ICZxdW90O2RBYjNiQWQmcXVvdDsgXHVkNjM5XHVjNzQwICZxdW90O0FkYjNiZEEmcXVvdDsgXHViODVjIFx1YmMxNFx1YjAxNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIDJcdWFjMWMgXHViYmY4XHViOWNjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWMwYmRcdWM3ODVcdWQ1NzRcdWMxMWNcdWIyOTQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NCBOICgzJmx0Oz1OJmx0Oz01MDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBOXHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWIzMDBcdWJiMzhcdWM3OTAgJiMzOTtBJiMzOTt+JiMzOTtaJiMzOTtcdWM2NDAgXHVjMThjXHViYjM4XHVjNzkwICYjMzk7YSYjMzk7fiYjMzk7eiYjMzk7LCBcdWMyMmJcdWM3OTAgMH45XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC4gXHViMzAwXHViYjM4XHVjNzkwXHVjNjQwIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1YjI5NCBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBiZFx1Yzc4NVx1ZDU3NFx1YzU3Y1x1ZDU2MCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NTAyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGFsaW5kcm9tZSIsImRlc2NyaXB0aW9uIjoiPHA+QSBwYWxpbmRyb21lIGlzIGEgc3ltbWV0cmljYWwgc3RyaW5nLCB0aGF0IGlzLCBhIHN0cmluZyByZWFkIGlkZW50aWNhbGx5IGZyb20gbGVmdCB0byByaWdodCBhcyB3ZWxsIGFzIGZyb20gcmlnaHQgdG8gbGVmdC4gWW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gd2hpY2gsIGdpdmVuIGEgc3RyaW5nLCBkZXRlcm1pbmVzIHRoZSBtaW5pbWFsIG51bWJlciBvZiBjaGFyYWN0ZXJzIHRvIGJlIGluc2VydGVkIGludG8gdGhlIHN0cmluZyBpbiBvcmRlciB0byBvYnRhaW4gYSBwYWxpbmRyb21lLjxcL3A+XHJcblxyXG48cD5BcyBhbiBleGFtcGxlLCBieSBpbnNlcnRpbmcgMiBjaGFyYWN0ZXJzLCB0aGUgc3RyaW5nICZxdW90O0FiM2JkJnF1b3Q7IGNhbiBiZSB0cmFuc2Zvcm1lZCBpbnRvIGEgcGFsaW5kcm9tZSAoJnF1b3Q7ZEFiM2JBZCZxdW90OyBvciAmcXVvdDtBZGIzYmRBJnF1b3Q7KS4gSG93ZXZlciwgaW5zZXJ0aW5nIGZld2VyIHRoYW4gMiBjaGFyYWN0ZXJzIGRvZXMgbm90IHByb2R1Y2UgYSBwYWxpbmRyb21lLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgb25lIGludGVnZXI6IHRoZSBsZW5ndGggb2YgdGhlIGlucHV0IHN0cmluZyBOLCAzJmxlO04mbGU7NTAwMC4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG9uZSBzdHJpbmcgd2l0aCBsZW5ndGggTi4gVGhlIHN0cmluZyBpcyBmb3JtZWQgZnJvbSB1cHBlcmNhc2UgbGV0dGVycyBmcm9tICZsc3F1bztBJnJzcXVvOyB0byAmbHNxdW87WiZyc3F1bzssIGxvd2VyY2FzZSBsZXR0ZXJzIGZyb20gJmxzcXVvO2EmcnNxdW87IHRvICZsc3F1bzt6JnJzcXVvOyBhbmQgZGlnaXRzIGZyb20gJmxzcXVvOzAmcnNxdW87IHRvICZsc3F1bzs5JnJzcXVvOy4gVXBwZXJjYXNlIGFuZCBsb3dlcmNhc2UgbGV0dGVycyBhcmUgdG8gYmUgY29uc2lkZXJlZCBkaXN0aW5jdC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBvbmUgaW50ZWdlciwgd2hpY2ggaXMgdGhlIGRlc2lyZWQgbWluaW1hbCBudW1iZXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > International Olympiad in Informatics > IOI 2000 1번