시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 174 54 42 35.294%

문제

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

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

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

입력

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

출력

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

예제 입력 1

letsgogogo

예제 출력 1

9

힌트

W3sicHJvYmxlbV9pZCI6IjIxMzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjNTU1XHVjZDk1XHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHVjMTFjIFx1ZDJiOVx1YzgxNVx1ZDU1YyBcdWQzMjhcdWQxMzRcdWM3NzQgXHViYzE4XHViY2Y1XHViNDIwIFx1YWNiZFx1YzZiMCwgXHVjNzc0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjODgwIFx1YjM1NCBcdWM5ZTdcdWFjOGMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjNTU1XHVjZDk1IFx1YWUzMFx1YmM5NVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWIyOTRcdWIzNzAsIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM1NTVcdWNkOTVcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTVjIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzAgXHVkNmE4XHVjNzI4XHVjODAxXHVjNzc4IFx1YmMyOVx1YmM5NVx1YjRlNFx1Yzc3NCBcdWM1ZjBcdWFkNmNcdWI0MThcdWM1YzhcdWIyZTQuIFJMRShSdW4gTGVuZ3RoIEVuY2RvaW5nKSBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjNzc0XHViN2VjXHVkNTVjIFx1YzU1NVx1Y2Q5NSBcdWJjMjlcdWJjOTUgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWFlMzBcdWNkMDhcdWM4MDFcdWM3NzggXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LiBSTEVcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHVjMTFjIFx1YzViNFx1YjVhNCBcdWJiMzhcdWM3OTBcdWFjMDAgXHViYzE4XHViY2Y1XHViNDIwIFx1YWNiZFx1YzZiMCwgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWQ1NWMgXHViYzg4XHViOWNjIFx1YzgwMFx1YzdhNVx1ZDU1OFx1YWNlMCBcdWFkZjggXHViMzAwXHVjMmUwIFx1YmMxOFx1YmNmNSBcdWQ2OGNcdWMyMThcdWI5N2MgXHVjODAwXHVjN2E1XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NFx1YjJlNC4gXHVjNzc0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YmE3NCBhYmNjZGRkXHViMjk0IGFiYzJkM1x1YzY0MCBcdWFjMTlcdWM3NzQgXHVjNTU1XHVjZDk1XHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1Yzc5MCBcdWIzMDBcdWMyZTAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YmE3NCBSTEVcdWI5N2MgXHVjODgwIFx1YjM1NCBcdWFjMWNcdWMxMjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHVjMTFjIFNcdWI3N2NcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IGtcdWJjODggXHViYzE4XHViY2Y1XHViNDIwIFx1YWNiZFx1YzZiMCwgXHVjNzc0XHViOTdjIGsoUylcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzJkZFx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBsZXRzZ29nb2dvXHViMjk0IGxldHMzKGdvKVx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjNTU1XHVjZDk1XHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjYmRcdWM2YjAgXHVjNmQwXHViNzk4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMTBcdWM3NzRcdWM5YzBcdWI5Y2MgXHVjNTU1XHVjZDk1XHViNDFjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgOVx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1YzU1NVx1Y2Q5NVx1YjQxYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU2MCBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVhZDA0XHVkNjM4XHVjNjQwIGtcdWI5N2MgXHViMDk4XHVkMGMwXHViMGJjIFx1YjU0YyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVhZTM4XHVjNzc0XHViM2M0IFx1ZDNlY1x1ZDU2OFx1ZDU3NFx1YzExYyBcdWFjYzRcdWMwYjBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHVjNTU1XHVjZDk1XHVjNzQ0IFx1YzkxMVx1Y2NhOVx1ZDU3NFx1YzExYyBcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBub3dsZXRzZ29nb2dvbGV0c2dvZ29nb1x1YjI5NCBub3cyKGxldHMzKGdvKSlcdWI4NWMsIG5vd2xldHNnb2dvZ29sZXRzZ29nb2dvYW5kcnVucnVucnVuIFx1Yzc0MCBub3cyKGxldHMzKGdvKSlhbmQzKHJ1bilcdWM3M2NcdWI4NWMgXHVjNTU1XHVjZDk1XHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWFjMWNcdWMxMjBcdWI0MWMgUkxFXHViYzI5XHViYzk1XHVjNWQwXHVjMTFjJm5ic3A7YWJjMmQzXHViODVjXHViMjk0IFx1YzU1NVx1Y2Q5NVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVhY2UwLCZuYnNwO2FiMihjKTMoZCkgXHViODVjXHViOWNjIFx1YzU1NVx1Y2Q5NVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0XHViOTdjIFx1YzU1NVx1Y2Q5NVx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjhcdWM5MDRcdWM1ZDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAyMDBcdWM3OTBcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCBcdWFjZjVcdWJjMzEgXHVjNWM2XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjhcdWM5MDRcdWM1ZDAgXHVjZDVjXHVjMThjIFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzU1NVx1Y2Q5NVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YjM1NCBcdWM5ZTdcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzZkMFx1Yjc5OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMTM1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RyaW5nIENvbXByZXNzaW9uIiwiZGVzY3JpcHRpb24iOiI8cD5SdW4gTGVuZ3RoIEVuY29kaW5nKFJMRSkgaXMgYSBzaW1wbGUgZm9ybSBvZiBjb21wcmVzc2lvbi4gUkxFIGNvbnNpc3RzIG9mIHRoZSBwcm9jZXNzIGZvciBzZWFyY2hpbmcgZm9yIGEgcmVwZWF0ZWQgcnVucyBvZiBhIHNpbmdsZSBjaGFyYWN0ZXIgaW4gYSBzdHJpbmcgdG8gYmUgY29tcHJlc3NlZCwgYW5kIHJlcGxhY2luZyB0aGVtIGJ5IGEgc2luZ2xlIGluc3RhbmNlIG9mIHRoZSBjaGFyYWN0ZXIgYW5kIGEgcnVuIGNvdW50LiBGb3IgZXhhbXBsZSwgYSBzdHJpbmcgYWJjY2NkZGRkZGRlZmdnZ2dnZ2dnZ2doaWprIGlzIGVuY29kZWQgaW50byBhIHN0cmluZyBhYjNjNmRlZjEwZ2hpamsgYnkgUkxFLjxcL3A+XHJcblxyXG48cD5BIG5ldyBjb21wcmVzc2lvbiBtZXRob2Qgc2ltaWxhciB0byBSTEUgaXMgZGV2aXNlZCBhbmQgdGhlIHJ1bGUgb2YgdGhlIG1ldGhvZCBpcyBhcyBmb2xsb3dzOiBpZiBhIHN1YnN0cmluZyBTIGlzIHJlcGVhdGVkIGsgdGltZXMsIHJlcGxhY2UgayBjb3BpZXMgb2YgUyBieSBrKFMpLiBGb3IgZXhhbXBsZSwgbGV0c2dvZ29nbyBpcyBjb21wcmVzc2VkIGludG8gbGV0czMoZ28pLiBUaGUgbGVuZ3RoIG9mIGxldHNnb2dvZ28gaXMgMTAsIGFuZCB0aGUgbGVuZ3RoIG9mIGxldHMzKGdvKSBpcyA5LiBJbiBnZW5lcmFsLCB0aGUgbGVuZ3RoIG9mIGsoUykgaXMgKG51bWJlciBvZiBkaWdpdHMgaW4gaykgKyAobGVuZ3RoIG9mIFMpICsgMiAoZm9yICZsc3F1bzsoJnJzcXVvOyBhbmQgJmxzcXVvOykmcnNxdW87KS4gRm9yIGV4YW1wbGUsIHRoZSBsZW5ndGggb2YgMTIzKGFiYykgaXMgOC4gSXQgaXMgYWxzbyBwb3NzaWJsZSB0byBuZXN0IGNvbXByZXNzaW9uLCBzbyB0aGUgc3Vic3RyaW5nIFMgbWF5IGl0c2VsZiBiZSBhIGNvbXByZXNzZWQgc3RyaW5nLiBGb3IgZXhhbXBsZSwgbm93bGV0c2dvZ29nb2xldHNnb2dvZ28gY291bGQgYmUgY29tcHJlc3NlZCBhcyBhIG5vdzIobGV0czMoZ28pKSwgYW5kIG5vd2xldHNnb2dvZ29sZXRzZ29nb2dvYW5kcnVucnVucnVuIGNvdWxkIGJlIGNvbXByZXNzZWQgYXMgbm93MihsZXRzMyhnbykpYW5kMyhydW4pLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZm9yIGEgZ2l2ZW4gc3RyaW5nLCBnaXZlcyBhIHNob3J0ZXN0IGNvbXByZXNzZWQgc3RyaW5nIHVzaW5nIHRoZSBjb21wcmVzc2lvbiBydWxlcyBhcyBkZXNjcmliZWQgYWJvdmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBvbmUgc3RyaW5nIG9mIG5vIG1vcmUgdGhhbiAyMDAgY2hhcmFjdGVycyBkcmF3biBmcm9tIGEgbG93ZXIgY2FzZSBhbHBoYWJldC4gVGhlIGxlbmd0aCBvZiBzaG9ydGVzdCBpbnB1dCBzdHJpbmcgaXMgMS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gRm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCB0aGUgbGVuZ3RoIG9mIHRoZSBzaG9ydGVzdCBjb21wcmVzc2VkIHN0cmluZy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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