시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB156574058250.565%

문제

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

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

입력

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

출력

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

예제 입력 1

5
Ab3bd

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjU1MDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1Yjc4MCBcdWIzMDBcdWNlNmQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LiZuYnNwO1x1Yzk4OSwgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWM3N2RcdWM1YzhcdWM3NDRcdWI1NGNcdWM2NDAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwXHVjMTFjIFx1YzY3Y1x1Y2FiZFx1YzczY1x1Yjg1YyBcdWM3N2RcdWM1YzhcdWM3NDRcdWI1NGMgXHVhYzE5XHViMmU0XHViMjk0IFx1YzU5OFx1YWUzMFx1YjJlNC4gXHViMmY5XHVjMmUwXHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDRcdWI1NGMsIFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWM3NTggXHViYjM4XHVjNzkwXHViOTdjJm5ic3A7XHVjMGJkXHVjNzg1XHVkNTU4XHVjNWVjIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWI0MThcdWFjOGMgXHViNDE4XHViMjk0IFx1YmIzOFx1Yzc5MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCwgMlx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjMGJkXHVjNzg1XHVkNTU4XHVjNWVjIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWI0MWNcdWIyZTQuICZxdW90O0FiM2JkJnF1b3Q7XHViMjk0ICZxdW90O2RBYjNiQWQmcXVvdDsgXHVkNjM5XHVjNzQwICZxdW90O0FkYjNiZEEmcXVvdDsgXHViODVjIFx1YmMxNFx1YjAxNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIDJcdWFjMWMgXHViYmY4XHViOWNjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWMwYmRcdWM3ODVcdWQ1NzRcdWMxMWNcdWIyOTQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NCBOICgzICZsZTsgTiAmbGU7IDUwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIE5cdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YjMwMFx1YmIzOFx1Yzc5MCAmIzM5O0EmIzM5Oy0mIzM5O1omIzM5O1x1YzY0MCBcdWMxOGNcdWJiMzhcdWM3OTAgJiMzOTthJiMzOTstJiMzOTt6JiMzOTssIFx1YzIyYlx1Yzc5MCAmIzM5OzAmIzM5Oy0mIzM5OzkmIzM5O1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjMwMFx1YmIzOFx1Yzc5MFx1YzY0MCBcdWMxOGNcdWJiMzhcdWM3OTBcdWIyOTQgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYmRcdWM3ODVcdWQ1NzRcdWM1N2NcdWQ1NjAgXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTUwMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBhbGluZHJvbWUiLCJkZXNjcmlwdGlvbiI6IjxwPkEgcGFsaW5kcm9tZSBpcyBhIHN5bW1ldHJpY2FsIHN0cmluZywgdGhhdCBpcywgYSBzdHJpbmcgcmVhZCBpZGVudGljYWxseSBmcm9tIGxlZnQgdG8gcmlnaHQgYXMgd2VsbCBhcyBmcm9tIHJpZ2h0IHRvIGxlZnQuIFlvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHdoaWNoLCBnaXZlbiBhIHN0cmluZywgZGV0ZXJtaW5lcyB0aGUgbWluaW1hbCBudW1iZXIgb2YgY2hhcmFjdGVycyB0byBiZSBpbnNlcnRlZCBpbnRvIHRoZSBzdHJpbmcgaW4gb3JkZXIgdG8gb2J0YWluIGEgcGFsaW5kcm9tZS48XC9wPlxyXG5cclxuPHA+QXMgYW4gZXhhbXBsZSwgYnkgaW5zZXJ0aW5nIDIgY2hhcmFjdGVycywgdGhlIHN0cmluZyAmcXVvdDtBYjNiZCZxdW90OyBjYW4gYmUgdHJhbnNmb3JtZWQgaW50byBhIHBhbGluZHJvbWUgKCZxdW90O2RBYjNiQWQmcXVvdDsgb3IgJnF1b3Q7QWRiM2JkQSZxdW90OykuIEhvd2V2ZXIsIGluc2VydGluZyBmZXdlciB0aGFuIDIgY2hhcmFjdGVycyBkb2VzIG5vdCBwcm9kdWNlIGEgcGFsaW5kcm9tZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyOiB0aGUgbGVuZ3RoIG9mIHRoZSBpbnB1dCBzdHJpbmcgTiwgMyAmbGU7IE4gJmxlOyA1MDAwLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgb25lIHN0cmluZyB3aXRoIGxlbmd0aCBOLiBUaGUgc3RyaW5nIGlzIGZvcm1lZCBmcm9tIHVwcGVyY2FzZSBsZXR0ZXJzIGZyb20gJmxzcXVvO0EmcnNxdW87IHRvICZsc3F1bztaJnJzcXVvOywgbG93ZXJjYXNlIGxldHRlcnMgZnJvbSAmbHNxdW87YSZyc3F1bzsgdG8gJmxzcXVvO3omcnNxdW87IGFuZCBkaWdpdHMgZnJvbSAmbHNxdW87MCZyc3F1bzsgdG8gJmxzcXVvOzkmcnNxdW87LiBVcHBlcmNhc2UgYW5kIGxvd2VyY2FzZSBsZXR0ZXJzIGFyZSB0byBiZSBjb25zaWRlcmVkIGRpc3RpbmN0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyLCB3aGljaCBpcyB0aGUgZGVzaXJlZCBtaW5pbWFsIG51bWJlci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > International Olympiad in Informatics > IOI 2000 > Day 1 1번