시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 10 4 4 44.444%

문제

어떤 수열이 주어졌을 때, 이 수열을 회전하면 여러 가지 수열을 얻을 수 있다. 이와 같이 수열을 회전하면서 얻은 수열들이 모두 원래의 수열보다 같거나 크면, 원래의 수열을 목걸이 수열이라 부른다. 예를 들어 01011은 목걸이 수열인데, 이는 10110, 01101, 11010, 10101, 01011 중에서 제일 작은 것이 원래의 01011이기 때문이다.

0과 1로 구성된 수열 S가 주어졌을 때, 이를 목걸이 수열들로 분해할 수 있다. 가장 간단한 방법은 각각의 숫자 단위로 분해하는 것인데, 그 외에도 다음의 조건을 만족하도록 분해할 수도 있다.

(1) 분해된 각각의 목걸이 수열들이 감소하는 순서대로 나타난다.

(2) 분해된 각각의 목걸이 수열들에 대해서, 인접한 두 개의 목걸이 수열을 붙였을 때 목걸이 수열을 이루지 않는다.

예를 들어 11101111011과 같은 수열이 있다고 했을 때, 이 수열은 (111)(01111)(011)로 분해할 수 있다. 이 경우 각각이 목걸이 수열임은 자명하고, 111 > 01111 > 011이 성립하며, 11101111과 011110111 중 어느 것도 목걸이 수열이 아니므로 위의 두 조건을 만족하는 예가 된다.


  0과 1로 이루어진 수열이 주어졌을 때, 위의 두 조건을 만족하도록 목걸이 수열들로 분해하는 방법을 찾아내는 프로그램을 작성하시오.

수열 사이의 대소 관계는 사전식 순서로 정의한다. 즉, A < B의 관계가 성립하는 경우는 A 뒤에 몇 글자를 붙이면 B가 되는 경우나, A와 B가 앞의 몇 개의 숫자가 같고 그 다음 숫자는 B에 있는 숫자가 더 큰 경우이다. 예를 들면 001 < 0010, 1101011 < 11011000이 성립한다. 이진수의 크기가 아님에 주의한다.

입력

첫째 0과 1로 이루어진 수열이 주어진다. 수열은 공백 없이 붙어서 주어지며, 그 길이는 1이상 100이하이다.

출력

첫재 줄에 목걸이 수열로 분해한 방법을 출력한다. 이를 위해서 각각의 목걸이 수열을 괄호로 묶어서 출력한다.

예제 입력 1

11101111011

예제 출력 1

(111)(01111)(011)

힌트

W3sicHJvYmxlbV9pZCI6IjIwNzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJhYTlcdWFjNzhcdWM3NzQgXHVjMjE4XHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVkNjhjXHVjODA0XHVkNTU4XHViYTc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzAgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWQ2OGNcdWM4MDRcdWQ1NThcdWJhNzRcdWMxMWMgXHVjNWJiXHVjNzQwIFx1YzIxOFx1YzVmNFx1YjRlNFx1Yzc3NCBcdWJhYThcdWI0NTAgXHVjNmQwXHViNzk4XHVjNzU4IFx1YzIxOFx1YzVmNFx1YmNmNFx1YjJlNCBcdWFjMTlcdWFjNzBcdWIwOTggXHVkMDZjXHViYTc0LCBcdWM2ZDBcdWI3OThcdWM3NTggXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YmFhOVx1YWM3OFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NzRcdWI3N2MgXHViZDgwXHViOTc4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IDAxMDExXHVjNzQwIFx1YmFhOVx1YWM3OFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NzhcdWIzNzAsIFx1Yzc3NFx1YjI5NCAxMDExMCwgMDExMDEsIDExMDEwLCAxMDEwMSwgMDEwMTEgXHVjOTExXHVjNWQwXHVjMTFjIFx1YzgxY1x1Yzc3YyBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzc0IFx1YzZkMFx1Yjc5OFx1Yzc1OCAwMTAxMVx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+MFx1YWNmYyAxXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxYyBcdWMyMThcdWM1ZjQgU1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzRcdWI5N2MgXHViYWE5XHVhYzc4XHVjNzc0IFx1YzIxOFx1YzVmNFx1YjRlNFx1Yjg1YyBcdWJkODRcdWQ1NzRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YWMwNFx1YjJlOFx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NDAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzIyYlx1Yzc5MCBcdWIyZThcdWM3MDRcdWI4NWMgXHViZDg0XHVkNTc0XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3OFx1YjM3MCwgXHVhZGY4IFx1YzY3OFx1YzVkMFx1YjNjNCBcdWIyZTRcdWM3NGNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWJkODRcdWQ1NzRcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG48cD4oMSkgXHViZDg0XHVkNTc0XHViNDFjIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJhYTlcdWFjNzhcdWM3NzQgXHVjMjE4XHVjNWY0XHViNGU0XHVjNzc0IFx1YWMxMFx1YzE4Y1x1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViMDk4XHVkMGMwXHViMDljXHViMmU0LjxcL3A+XHJcbjxwPigyKSBcdWJkODRcdWQ1NzRcdWI0MWMgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmFhOVx1YWM3OFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWI0ZTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWJhYTlcdWFjNzhcdWM3NzQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YmQ5OVx1YzYwMFx1Yzc0NCBcdWI1NGMgXHViYWE5XHVhYzc4XHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgMTExMDExMTEwMTFcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0MCAoMTExKSgwMTExMSkoMDExKVx1Yjg1YyBcdWJkODRcdWQ1NzRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWNiZFx1YzZiMCBcdWFjMDFcdWFjMDFcdWM3NzQgXHViYWE5XHVhYzc4XHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc4NFx1Yzc0MCBcdWM3OTBcdWJhODVcdWQ1NThcdWFjZTAsIDExMSAmZ3Q7IDAxMTExICZndDsgMDExXHVjNzc0IFx1YzEzMVx1YjliZFx1ZDU1OFx1YmE3MCwgMTExMDExMTFcdWFjZmMgMDExMTEwMTExIFx1YzkxMSBcdWM1YjRcdWIyOTAgXHVhYzgzXHViM2M0IFx1YmFhOVx1YWM3OFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNTQ0XHViMmM4XHViYmMwXHViODVjIFx1YzcwNFx1Yzc1OCBcdWI0NTAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWM2MDhcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcbjxwPjxiciBcLz5cclxuJm5ic3A7IDBcdWFjZmMgMVx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzcwNFx1Yzc1OCBcdWI0NTAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWJhYTlcdWFjNzhcdWM3NzQgXHVjMjE4XHVjNWY0XHViNGU0XHViODVjIFx1YmQ4NFx1ZDU3NFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjYzNlXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuPHA+XHVjMjE4XHVjNWY0IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWIzMDBcdWMxOGMgXHVhZDAwXHVhY2M0XHViMjk0IFx1YzBhY1x1YzgwNFx1YzJkZCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LiBcdWM5ODksIEEgJmx0OyBCXHVjNzU4IFx1YWQwMFx1YWNjNFx1YWMwMCBcdWMxMzFcdWI5YmRcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IEEgXHViNGE0XHVjNWQwIFx1YmE4NyBcdWFlMDBcdWM3OTBcdWI5N2MgXHViZDk5XHVjNzc0XHViYTc0IEJcdWFjMDAgXHViNDE4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjA5OCwgQVx1YzY0MCBCXHVhYzAwIFx1YzU1ZVx1Yzc1OCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWFjMTlcdWFjZTAgXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWMyMmJcdWM3OTBcdWIyOTQgQlx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YjM1NCBcdWQwNzAgXHVhY2JkXHVjNmIwXHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0IDAwMSAmbHQ7IDAwMTAsIDExMDEwMTEgJmx0OyAxMTAxMTAwMFx1Yzc3NCBcdWMxMzFcdWI5YmRcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YzljNFx1YzIxOFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVjNTQ0XHViMmQ4XHVjNWQwIFx1YzhmY1x1Yzc1OFx1ZDU1Y1x1YjJlNC48XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IDBcdWFjZmMgMVx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMjE4XHVjNWY0XHVjNzQwIFx1YWNmNVx1YmMzMSBcdWM1YzZcdWM3NzQgXHViZDk5XHVjNWI0XHVjMTFjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVhZGY4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxXHVjNzc0XHVjMGMxIDEwMFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzdhYyBcdWM5MDRcdWM1ZDAgXHViYWE5XHVhYzc4XHVjNzc0IFx1YzIxOFx1YzVmNFx1Yjg1YyBcdWJkODRcdWQ1NzRcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViOTdjIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWFjMDFcdWFjMDFcdWM3NTggXHViYWE5XHVhYzc4XHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWFkMDRcdWQ2MzhcdWI4NWMgXHViYjM2XHVjNWI0XHVjMTFjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIwNzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOZWNrbGFjZSBEZWNvbXBvc2l0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgc2V0IG9mIGN5Y2xpYyByb3RhdGlvbnMgb2YgYSBzdHJpbmcgYXJlIHRoZSBzdHJpbmdzIG9idGFpbmVkIGJ5IGVtYmVkZGluZyB0aGUgc3RyaW5nIGNsb2Nrd2lzZSBvbiBhIHJpbmcsIHdpdGggdGhlIGZpcnN0IGNoYXJhY3RlciBmb2xsb3dpbmcgb24gdGhlIGxhc3QsIHN0YXJ0aW5nIGF0IGFueSBjaGFyYWN0ZXIgcG9zaXRpb24gYW5kIG1vdmluZyBjbG9ja3dpc2Ugb24gdGhlIHJpbmcgdW50aWwgdGhlIGNoYXJhY3RlciBwcmVjZWVkaW5nIHRoZSBzdGFydGluZyBjaGFyYWN0ZXIgaXMgcmVhY2hlZC4gQSBzdHJpbmcgaXMgYSBuZWNrbGFjZSBpZiBpdCBpcyB0aGUgbGV4aWNvZ3JhcGhpY2FsbHkgc21hbGxlc3QgYW1vbmcgYWxsIGl0cyBjeWNsaWMgcm90YXRpb25zLiBGb3IgaW5zdGFuY2UsIGZvciB0aGUgc3RyaW5nIDAxMDExIHRoZSBjeWNsaWMgcm90YXRpb25zIGFyZSAoMTAxMTAsMDExMDEsMTEwMTAsMTAxMDEsMDEwMTEpLCBhbmQgZnVydGhlcm1vcmUgMDEwMTEgaXMgdGhlIHNtYWxsZXN0IHN0cmluZyBhbmQgaGVuY2UsIGEgbmVja2xhY2UuPFwvcD5cclxuXHJcbjxwPkFueSBzdHJpbmcgUyBjYW4gYmUgd3JpdHRlbiBpbiBhIHVuaXF1ZSB3YXkgYXMgYSBjb25jYXRlbmF0aW9uIFMgPSBUMVQyLi4uVGsgb2YgbmVja2xhY2VzIFRpIHN1Y2ggdGhhdCBUaSsxICZsdDsgVGkgZm9yIGFsbCBpID0gMSwuLi4gLCBrICZtaW51czsgMSwgYW5kIFRpVGkrMSBpcyBub3QgYSBuZWNrbGFjZSBmb3IgYW55IGkgPSAxLC4uLiAsIGsgJm1pbnVzOyAxLiBUaGlzIHJlcHJlc2VudGF0aW9uIGlzIGNhbGxlZCB0aGUgbmVja2xhY2UgZGVjb21wb3NpdGlvbiBvZiB0aGUgc3RyaW5nIFMsIGFuZCB5b3VyIHRhc2sgaXMgdG8gZmluZCBpdC48XC9wPlxyXG5cclxuPHA+VGhlIHJlbGF0aW9uICZsdDsgb24gdHdvIHN0cmluZ3MgaXMgdGhlIGxleGljb2dyYXBoaWNhbCBvcmRlciBhbmQgaGFzIHRoZSB1c3VhbCBpbnRlcnByZXRhdGlvbjogQSAmbHQ7IEIgaWYgQSBpcyBhIHByb3BlciBwcmVmaXggb2YgQiBvciBpZiBBIGlzIGVxdWFsIHRvIEIgaW4gdGhlIGZpcnN0IGogJm1pbnVzOyAxIHBvc2l0aW9ucyBidXQgc21hbGxlciBpbiB0aGUganRoIHBvc2l0aW9uIGZvciBzb21lIGouIEZvciBpbnN0YW5jZSwgMDAxICZsdDsgMDAxMCBhbmQgMTEwMTAxMSAmbHQ7IDExMDExMDAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgaXMgYSBzaW5nbGUgcG9zaXRpdmUgaW50ZWdlciBuLCB0ZWxsaW5nIHRoZSBudW1iZXIgb2YgdGVzdCBzY2VuYXJpb3MgdG8gZm9sbG93LiBFYWNoIHNjZW5hcmlvIGNvbnNpc3RzIG9mIG9uZSBsaW5lIGNvbnRhaW5pbmcgYSBub24tZW1wdHkgc3RyaW5nIG9mIHplcm9zIGFuZCBvbmVzIG9mIGxlbmd0aCBhdCBtb3N0IDEwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBzY2VuYXJpbywgb3V0cHV0IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG5lY2tsYWNlIGRlY29tcG9zaXRpb24gb2YgdGhlIHN0cmluZy4gVGhlIG5lY2tsYWNlcyBzaG91bGQgYmUgd3JpdHRlbiBhcyAmcnNxdW87KCZyc3F1bzsgbmVja2xhY2UgJnJzcXVvOykmcnNxdW87LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==