시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB129442934942.509%

문제

팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다.

만일 어떤 단어가 팰린드롬이 아니라면, 그 단어는 여러 개의 팰린드롬으로 나누어질 수 있을 것이다. 단어가 주어졌을 때 이를 여러 개의 팰린드롬으로 나누되, 나누어진 팰린드롬의 개수가 최소가 되도록 나누려고 한다.

예를 들어 abaccbcb라는 문자는 aba, cc, bcb와 같이 세 개의 문자열로 나누면 각각 팰린드롬이 된다. 하지만 두 개의 문자열로 나누어서는 결코 각각이 모두 팰린드롬이 될 수 없다. 따라서 이 경우의 답은 3이다. 마찬가지로 anavolimilana와 같은 문자열은 ana, v, o, limil, ana의 다섯 개의 문자열로 나누면 각각 팰린드롬으로 만들 수 있으며, 네 개로 나누어서는 각각이 모두 팰린드롬이 되도록 만들 수 없다. 따라서 이 경우의 답은 5이다.

문자열이 주어졌을 때, 이 문자열을 최소 개수의 팰린드롬으로 나누는 프로그램을 작성하시오. 문자열 자체가 팰린드롬이라면 굳이 나눌 필요는 없다.

입력

첫째 줄에 단어가 입력으로 들어온다. 단어는 영어 소문자로만 이루어져 있으며, 그 길이는 2,000을 넘지 않는다.

출력

주어진 문자열을 최소 개수의 팰린드롬으로 나누었을 때, 그 개수를 출력한다.

예제 입력 1

anaban

예제 출력 1

2

예제 입력 2

abaccbcb

예제 출력 2

3

예제 입력 3

anavolimilana

예제 출력 3

5
W3sicHJvYmxlbV9pZCI6IjIwNzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2YyhwYWxpbmRyb21lKVx1Yzc3NFx1Yjc4MCBcdWM1NWVcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjNzdkXHVjNzNjXHViMDk4IFx1YjRhNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBcdWM3N2RcdWM3M2NcdWIwOTggXHVhYzE5XHVjNzQwIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWI5ZDBcdWQ1NWNcdWIyZTQuICYjMzk7YWJhJiMzOTtcdWIwOTggJiMzOTthJiMzOTtcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YjJlOFx1YzViNFx1YjI5NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzRcdWJhNzAsICYjMzk7YWJhY2NiY2ImIzM5O1x1YjA5OCAmIzM5O2FuYXZvbGltaWxhbmEmIzM5O1x1YzY0MCBcdWFjMTlcdWM3NDAgXHViMmU4XHVjNWI0XHViMjk0IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1Yzc3YyBcdWM1YjRcdWI1YTQgXHViMmU4XHVjNWI0XHVhYzAwIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWM1NDRcdWIyYzhcdWI3N2NcdWJhNzQsIFx1YWRmOCBcdWIyZThcdWM1YjRcdWIyOTQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWIyZThcdWM1YjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWM3NzRcdWI5N2MgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHViNDE4LCBcdWIwOThcdWIyMDRcdWM1YjRcdWM5YzQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YjA5OFx1YjIwNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgYWJhY2NiY2JcdWI3N2NcdWIyOTQgXHViYjM4XHVjNzkwXHViMjk0IGFiYSwgY2MsIGJjYlx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViMDk4XHViMjA0XHViYTc0IFx1YWMwMVx1YWMwMSBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzQgXHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjMTFjXHViMjk0IFx1YWNiMFx1Y2Y1NCBcdWFjMDFcdWFjMDFcdWM3NzQgXHViYWE4XHViNDUwIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWI0MjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWM3NTggXHViMmY1XHVjNzQwIDNcdWM3NzRcdWIyZTQuIFx1YjljOFx1Y2MyY1x1YWMwMFx1YzljMFx1Yjg1YyBhbmF2b2xpbWlsYW5hXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgYW5hLCB2LCBvLCBsaW1pbCwgYW5hXHVjNzU4IFx1YjJlNFx1YzEyZiBcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YjA5OFx1YjIwNFx1YmE3NCBcdWFjMDFcdWFjMDEgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWIxMjQgXHVhYzFjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzExY1x1YjI5NCBcdWFjMDFcdWFjMDFcdWM3NzQgXHViYWE4XHViNDUwIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWI0MThcdWIzYzRcdWI4NWQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM3NzQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YjJmNVx1Yzc0MCA1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHVjNzU4IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViYjM4XHVjNzkwXHVjNWY0IFx1Yzc5MFx1Y2NiNFx1YWMwMCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzRcdWI3N2NcdWJhNzQgXHVhZDczXHVjNzc0IFx1YjA5OFx1YjIwYyBcdWQ1NDRcdWM2OTRcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC4gXHViMmU4XHVjNWI0XHViMjk0IFx1YzYwMVx1YzViNCBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZGY4IFx1YWUzOFx1Yzc3NFx1YjI5NCAyLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzhmY1x1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjA3OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBBTElOIiwiZGVzY3JpcHRpb24iOiI8cD5BIHBhbGluZHJvbWUgaXMgYSB3b3JkIHRoYXQgaXMgcmVhZCB0aGUgc2FtZSBmb3J3YXJkIG9yIGJhY2t3YXJkcy4gSWYgYSB3b3JkIGlzIG5vdCBhIHBhbGluZHJvbWUsIGl0IGNhbiBiZSBjdXQgaW50byBwYXJ0cyB0aGF0IGFyZSBwYWxpbmRyb21lcy4gV3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBjYWxjdWxhdGUgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBwYWxpbmRyb21lIHBhcnRzIHRvIHdoaWNoIGEgZ2l2ZW4gc2VxdWVuY2Ugb2YgY2hhcmFjdGVycyBjYW4gYmUgY3V0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgZmlsZSBjb250YWlucyBhIHNlcXVlbmNlIG9mIGNoYXJhY3RlcnMuIFRoZSBjaGFyYWN0ZXJzIHVzZWQgYXMgaW5wdXQgd2lsbCBiZSBmcm9tIHRoZSBzZXQgb2Ygc21hbGwgbGV0dGVycyBvZiBFbmdsaXNoIGFscGhhYmV0IChhJm5kYXNoO3opLiBUaGUgbGVuZ3RoIG9mIGV2ZXJ5IGlucHV0IHNlcXVlbmNlIHdpbGwgYmUgYXQgbW9zdCAyMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBmaWxlIHNob3VsZCBjb250YWluIHJlcXVpcmVkIG51bWJlciBvZiBwYWxpbmRyb21lcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2001 > Regional Competition - Seniors 4번

  • 빠진 조건을 찾은 사람: doju
  • 잘못된 데이터를 찾은 사람: nova9128