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

문제

어떤 문자열에서 특정한 패턴이 반복될 경우, 이를 이용하여 문자열을 좀 더 짧게 나타낼 수도 있다. 이러한 방법을 압축 기법이라고 하는데, 문자열을 압축하기 위한 여러 가지 효율적인 방법들이 연구되었다. RLE(Run Length Encdoing) 방법은 이러한 압축 방법 중 가장 기초적인 방법이다. RLE는 문자열에서 어떤 문자가 반복될 경우, 이 문자를 한 번만 저장하고 그 대신 반복 회수를 저장하는 방법이다. 이를 이용하면 abccdddabc2d3와 같이 압축될 수 있다.

문자 대신 문자열을 이용하면 RLE를 좀 더 개선할 수 있다. 예를 들어 주어진 문자열에서 S라는 문자열이 k번 반복될 경우, 이를 k(S)와 같은 식으로 표현할 수 있다. 예를 들어 letsgogogolets3(go)와 같이 압축될 수 있다. 이 경우 원래 문자열의 길이는 10이지만 압축된 문자열의 길이는 9가 된다. 압축된 문자열의 길이를 계산할 때에는 괄호와 k를 나타낼 때 필요한 길이도 포함해서 계산한다. 또, 압축을 중첩해서 할 수도 있는데, 예를 들어 nowletsgogogoletsgogogonow2(lets3(go))로, nowletsgogogoletsgogogoandrunrunrunnow2(lets3(go))and3(run)으로 압축될 수 있다. 이렇게 개선된 RLE방법에서 abc2d3로는 압축할 수 없고, ab2(c)3(d) 로만 압축할 수 있다.

문자열이 주어졌을 때, 이를 압축하는 방법은 여러 가지가 있을 수 있다. 그 중 가장 짧은 방법의 길이를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 알파벳 소문자로 이루어진 문자열이 주어진다. 문자열의 길이는 200자를 넘지 않으며 공백 없이 주어진다.

출력

첫째 줄에 최소 길이를 출력한다. 압축하지 않는 경우가 더 짧은 경우에는 원래 문자열의 길이를 출력한다.

예제 입력 1

letsgogogo

예제 출력 1

9

예제 입력 2

abc

예제 출력 2

3
W3sicHJvYmxlbV9pZCI6IjIxMzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjNTU1XHVjZDk1XHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHVjMTFjIFx1ZDJiOVx1YzgxNVx1ZDU1YyBcdWQzMjhcdWQxMzRcdWM3NzQgXHViYzE4XHViY2Y1XHViNDIwIFx1YWNiZFx1YzZiMCwgXHVjNzc0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjODgwIFx1YjM1NCBcdWM5ZTdcdWFjOGMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjNTU1XHVjZDk1IFx1YWUzMFx1YmM5NVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWIyOTRcdWIzNzAsIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM1NTVcdWNkOTVcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTVjIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzAgXHVkNmE4XHVjNzI4XHVjODAxXHVjNzc4IFx1YmMyOVx1YmM5NVx1YjRlNFx1Yzc3NCBcdWM1ZjBcdWFkNmNcdWI0MThcdWM1YzhcdWIyZTQuIFJMRShSdW4gTGVuZ3RoIEVuY2RvaW5nKSBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjNzc0XHViN2VjXHVkNTVjIFx1YzU1NVx1Y2Q5NSBcdWJjMjlcdWJjOTUgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWFlMzBcdWNkMDhcdWM4MDFcdWM3NzggXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LiBSTEVcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHVjMTFjIFx1YzViNFx1YjVhNCBcdWJiMzhcdWM3OTBcdWFjMDAgXHViYzE4XHViY2Y1XHViNDIwIFx1YWNiZFx1YzZiMCwgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWQ1NWMgXHViYzg4XHViOWNjIFx1YzgwMFx1YzdhNVx1ZDU1OFx1YWNlMCBcdWFkZjggXHViMzAwXHVjMmUwIFx1YmMxOFx1YmNmNSBcdWQ2OGNcdWMyMThcdWI5N2MgXHVjODAwXHVjN2E1XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NFx1YjJlNC4gXHVjNzc0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YmE3NCA8Y29kZT5hYmNjZGRkPFwvY29kZT5cdWIyOTQgPGNvZGU+YWJjMmQzPFwvY29kZT5cdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzU1NVx1Y2Q5NVx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3OTAgXHViMzAwXHVjMmUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NThcdWJhNzQgUkxFXHViOTdjIFx1Yzg4MCBcdWIzNTQgXHVhYzFjXHVjMTIwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMFx1YzExYyBTXHViNzdjXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBrXHViYzg4IFx1YmMxOFx1YmNmNVx1YjQyMCBcdWFjYmRcdWM2YjAsIFx1Yzc3NFx1Yjk3YyBrKFMpXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMyZGRcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgPGNvZGU+bGV0c2dvZ29nbzxcL2NvZGU+XHViMjk0IDxjb2RlPmxldHMzKGdvKTxcL2NvZGU+XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM1NTVcdWNkOTVcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWNiZFx1YzZiMCBcdWM2ZDBcdWI3OTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxMFx1Yzc3NFx1YzljMFx1YjljYyBcdWM1NTVcdWNkOTVcdWI0MWMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCA5XHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVjNTU1XHVjZDk1XHViNDFjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTYwIFx1YjU0Y1x1YzVkMFx1YjI5NCBcdWFkMDRcdWQ2MzhcdWM2NDAga1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYmMgXHViNTRjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWFlMzhcdWM3NzRcdWIzYzQgXHVkM2VjXHVkNTY4XHVkNTc0XHVjMTFjIFx1YWNjNFx1YzBiMFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWM1NTVcdWNkOTVcdWM3NDQgXHVjOTExXHVjY2E5XHVkNTc0XHVjMTFjIFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMjk0XHViMzcwLCBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IDxjb2RlPm5vd2xldHNnb2dvZ29sZXRzZ29nb2dvPFwvY29kZT5cdWIyOTQgPGNvZGU+bm93MihsZXRzMyhnbykpPFwvY29kZT5cdWI4NWMsIDxjb2RlPm5vd2xldHNnb2dvZ29sZXRzZ29nb2dvYW5kcnVucnVucnVuPFwvY29kZT4gXHVjNzQwIDxjb2RlPm5vdzIobGV0czMoZ28pKWFuZDMocnVuKTxcL2NvZGU+XHVjNzNjXHViODVjIFx1YzU1NVx1Y2Q5NVx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVhYzFjXHVjMTIwXHViNDFjIFJMRVx1YmMyOVx1YmM5NVx1YzVkMFx1YzExYyZuYnNwO2FiYzJkM1x1Yjg1Y1x1YjI5NCBcdWM1NTVcdWNkOTVcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YWNlMCwmbmJzcDs8Y29kZT5hYjIoYykzKGQpPFwvY29kZT4gXHViODVjXHViOWNjIFx1YzU1NVx1Y2Q5NVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0XHViOTdjIFx1YzU1NVx1Y2Q5NVx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMjAwXHVjNzkwXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAgXHVhY2Y1XHViYzMxIFx1YzVjNlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNkNWNcdWMxOGMgXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNTU1XHVjZDk1XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHViMzU0IFx1YzllN1x1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNmQwXHViNzk4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIxMzUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdHJpbmcgQ29tcHJlc3Npb24iLCJkZXNjcmlwdGlvbiI6IjxwPlJ1biBMZW5ndGggRW5jb2RpbmcoUkxFKSBpcyBhIHNpbXBsZSBmb3JtIG9mIGNvbXByZXNzaW9uLiBSTEUgY29uc2lzdHMgb2YgdGhlIHByb2Nlc3MgZm9yIHNlYXJjaGluZyBmb3IgYSByZXBlYXRlZCBydW5zIG9mIGEgc2luZ2xlIGNoYXJhY3RlciBpbiBhIHN0cmluZyB0byBiZSBjb21wcmVzc2VkLCBhbmQgcmVwbGFjaW5nIHRoZW0gYnkgYSBzaW5nbGUgaW5zdGFuY2Ugb2YgdGhlIGNoYXJhY3RlciBhbmQgYSBydW4gY291bnQuIEZvciBleGFtcGxlLCBhIHN0cmluZyBhYmNjY2RkZGRkZGVmZ2dnZ2dnZ2dnZ2hpamsgaXMgZW5jb2RlZCBpbnRvIGEgc3RyaW5nIGFiM2M2ZGVmMTBnaGlqayBieSBSTEUuPFwvcD5cclxuXHJcbjxwPkEgbmV3IGNvbXByZXNzaW9uIG1ldGhvZCBzaW1pbGFyIHRvIFJMRSBpcyBkZXZpc2VkIGFuZCB0aGUgcnVsZSBvZiB0aGUgbWV0aG9kIGlzIGFzIGZvbGxvd3M6IGlmIGEgc3Vic3RyaW5nIFMgaXMgcmVwZWF0ZWQgayB0aW1lcywgcmVwbGFjZSBrIGNvcGllcyBvZiBTIGJ5IGsoUykuIEZvciBleGFtcGxlLCBsZXRzZ29nb2dvIGlzIGNvbXByZXNzZWQgaW50byBsZXRzMyhnbykuIFRoZSBsZW5ndGggb2YgbGV0c2dvZ29nbyBpcyAxMCwgYW5kIHRoZSBsZW5ndGggb2YgbGV0czMoZ28pIGlzIDkuIEluIGdlbmVyYWwsIHRoZSBsZW5ndGggb2YgayhTKSBpcyAobnVtYmVyIG9mIGRpZ2l0cyBpbiBrKSArIChsZW5ndGggb2YgUykgKyAyIChmb3IgJmxzcXVvOygmcnNxdW87IGFuZCAmbHNxdW87KSZyc3F1bzspLiBGb3IgZXhhbXBsZSwgdGhlIGxlbmd0aCBvZiAxMjMoYWJjKSBpcyA4LiBJdCBpcyBhbHNvIHBvc3NpYmxlIHRvIG5lc3QgY29tcHJlc3Npb24sIHNvIHRoZSBzdWJzdHJpbmcgUyBtYXkgaXRzZWxmIGJlIGEgY29tcHJlc3NlZCBzdHJpbmcuIEZvciBleGFtcGxlLCBub3dsZXRzZ29nb2dvbGV0c2dvZ29nbyBjb3VsZCBiZSBjb21wcmVzc2VkIGFzIGEgbm93MihsZXRzMyhnbykpLCBhbmQgbm93bGV0c2dvZ29nb2xldHNnb2dvZ29hbmRydW5ydW5ydW4gY291bGQgYmUgY29tcHJlc3NlZCBhcyBub3cyKGxldHMzKGdvKSlhbmQzKHJ1bikuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBmb3IgYSBnaXZlbiBzdHJpbmcsIGdpdmVzIGEgc2hvcnRlc3QgY29tcHJlc3NlZCBzdHJpbmcgdXNpbmcgdGhlIGNvbXByZXNzaW9uIHJ1bGVzIGFzIGRlc2NyaWJlZCBhYm92ZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5pbmcgb25lIHN0cmluZyBvZiBubyBtb3JlIHRoYW4gMjAwIGNoYXJhY3RlcnMgZHJhd24gZnJvbSBhIGxvd2VyIGNhc2UgYWxwaGFiZXQuIFRoZSBsZW5ndGggb2Ygc2hvcnRlc3QgaW5wdXQgc3RyaW5nIGlzIDEuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIGxlbmd0aCBvZiB0aGUgc2hvcnRlc3QgY29tcHJlc3NlZCBzdHJpbmcuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Seoul 2005 J번

  • 빠진 조건을 찾은 사람: koosaga