시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 176 55 43 35.833%

문제

어떤 문자열에서 특정한 패턴이 반복될 경우, 이를 이용하여 문자열을 좀 더 짧게 나타낼 수도 있다. 이러한 방법을 압축 기법이라고 하는데, 문자열을 압축하기 위한 여러 가지 효율적인 방법들이 연구되었다. 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+XHJcblxyXG48cD5cdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0XHViOTdjIFx1YzU1NVx1Y2Q5NVx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMjAwXHVjNzkwXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAgXHVhY2Y1XHViYzMxIFx1YzVjNlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNkNWNcdWMxOGMgXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNTU1XHVjZDk1XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHViMzU0IFx1YzllN1x1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNmQwXHViNzk4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIxMzUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTdHJpbmcgQ29tcHJlc3Npb24iLCJkZXNjcmlwdGlvbiI6IjxwPlJ1biBMZW5ndGggRW5jb2RpbmcoUkxFKSBpcyBhIHNpbXBsZSBmb3JtIG9mIGNvbXByZXNzaW9uLiBSTEUgY29uc2lzdHMgb2YgdGhlIHByb2Nlc3MgZm9yIHNlYXJjaGluZyBmb3IgYSByZXBlYXRlZCBydW5zIG9mIGEgc2luZ2xlIGNoYXJhY3RlciBpbiBhIHN0cmluZyB0byBiZSBjb21wcmVzc2VkLCBhbmQgcmVwbGFjaW5nIHRoZW0gYnkgYSBzaW5nbGUgaW5zdGFuY2Ugb2YgdGhlIGNoYXJhY3RlciBhbmQgYSBydW4gY291bnQuIEZvciBleGFtcGxlLCBhIHN0cmluZyBhYmNjY2RkZGRkZGVmZ2dnZ2dnZ2dnZ2hpamsgaXMgZW5jb2RlZCBpbnRvIGEgc3RyaW5nIGFiM2M2ZGVmMTBnaGlqayBieSBSTEUuPFwvcD5cclxuXHJcbjxwPkEgbmV3IGNvbXByZXNzaW9uIG1ldGhvZCBzaW1pbGFyIHRvIFJMRSBpcyBkZXZpc2VkIGFuZCB0aGUgcnVsZSBvZiB0aGUgbWV0aG9kIGlzIGFzIGZvbGxvd3M6IGlmIGEgc3Vic3RyaW5nIFMgaXMgcmVwZWF0ZWQgayB0aW1lcywgcmVwbGFjZSBrIGNvcGllcyBvZiBTIGJ5IGsoUykuIEZvciBleGFtcGxlLCBsZXRzZ29nb2dvIGlzIGNvbXByZXNzZWQgaW50byBsZXRzMyhnbykuIFRoZSBsZW5ndGggb2YgbGV0c2dvZ29nbyBpcyAxMCwgYW5kIHRoZSBsZW5ndGggb2YgbGV0czMoZ28pIGlzIDkuIEluIGdlbmVyYWwsIHRoZSBsZW5ndGggb2YgayhTKSBpcyAobnVtYmVyIG9mIGRpZ2l0cyBpbiBrKSArIChsZW5ndGggb2YgUykgKyAyIChmb3IgJmxzcXVvOygmcnNxdW87IGFuZCAmbHNxdW87KSZyc3F1bzspLiBGb3IgZXhhbXBsZSwgdGhlIGxlbmd0aCBvZiAxMjMoYWJjKSBpcyA4LiBJdCBpcyBhbHNvIHBvc3NpYmxlIHRvIG5lc3QgY29tcHJlc3Npb24sIHNvIHRoZSBzdWJzdHJpbmcgUyBtYXkgaXRzZWxmIGJlIGEgY29tcHJlc3NlZCBzdHJpbmcuIEZvciBleGFtcGxlLCBub3dsZXRzZ29nb2dvbGV0c2dvZ29nbyBjb3VsZCBiZSBjb21wcmVzc2VkIGFzIGEgbm93MihsZXRzMyhnbykpLCBhbmQgbm93bGV0c2dvZ29nb2xldHNnb2dvZ29hbmRydW5ydW5ydW4gY291bGQgYmUgY29tcHJlc3NlZCBhcyBub3cyKGxldHMzKGdvKSlhbmQzKHJ1bikuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBmb3IgYSBnaXZlbiBzdHJpbmcsIGdpdmVzIGEgc2hvcnRlc3QgY29tcHJlc3NlZCBzdHJpbmcgdXNpbmcgdGhlIGNvbXByZXNzaW9uIHJ1bGVzIGFzIGRlc2NyaWJlZCBhYm92ZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIG9uZSBzdHJpbmcgb2Ygbm8gbW9yZSB0aGFuIDIwMCBjaGFyYWN0ZXJzIGRyYXduIGZyb20gYSBsb3dlciBjYXNlIGFscGhhYmV0LiBUaGUgbGVuZ3RoIG9mIHNob3J0ZXN0IGlucHV0IHN0cmluZyBpcyAxLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBGb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IHRoZSBsZW5ndGggb2YgdGhlIHNob3J0ZXN0IGNvbXByZXNzZWQgc3RyaW5nLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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