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

문제

어떤 수열이 주어졌을 때, 이 수열을 회전하면 여러 가지 수열을 얻을 수 있다. 이와 같이 수열을 회전하면서 얻은 수열들이 모두 원래의 수열보다 같거나 크면, 원래의 수열을 목걸이 수열이라 부른다. 예를 들어 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)

예제 입력 2

0001

예제 출력 2

(0001)
W3sicHJvYmxlbV9pZCI6IjIwNzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJhYTlcdWFjNzhcdWM3NzQgXHVjMjE4XHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVkNjhjXHVjODA0XHVkNTU4XHViYTc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzAgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWQ2OGNcdWM4MDRcdWQ1NThcdWJhNzRcdWMxMWMgXHVjNWJiXHVjNzQwIFx1YzIxOFx1YzVmNFx1YjRlNFx1Yzc3NCBcdWJhYThcdWI0NTAgXHVjNmQwXHViNzk4XHVjNzU4IFx1YzIxOFx1YzVmNFx1YmNmNFx1YjJlNCBcdWFjMTlcdWFjNzBcdWIwOTggXHVkMDZjXHViYTc0LCBcdWM2ZDBcdWI3OThcdWM3NTggXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YmFhOVx1YWM3OFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NzRcdWI3N2MgXHViZDgwXHViOTc4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IDAxMDExXHVjNzQwIFx1YmFhOVx1YWM3OFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NzhcdWIzNzAsIFx1Yzc3NFx1YjI5NCAxMDExMCwgMDExMDEsIDExMDEwLCAxMDEwMSwgMDEwMTEgXHVjOTExXHVjNWQwXHVjMTFjIFx1YzgxY1x1Yzc3YyBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzc0IFx1YzZkMFx1Yjc5OFx1Yzc1OCAwMTAxMVx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjBcdWFjZmMgMVx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWMgXHVjMjE4XHVjNWY0IFNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0XHViOTdjIFx1YmFhOVx1YWM3OFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWI0ZTRcdWI4NWMgXHViZDg0XHVkNTc0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWFjMDRcdWIyZThcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzQwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMyMmJcdWM3OTAgXHViMmU4XHVjNzA0XHViODVjIFx1YmQ4NFx1ZDU3NFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzhcdWIzNzAsIFx1YWRmOCBcdWM2NzhcdWM1ZDBcdWIzYzQgXHViMmU0XHVjNzRjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIzYzRcdWI4NWQgXHViZDg0XHVkNTc0XHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHViZDg0XHVkNTc0XHViNDFjIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJhYTlcdWFjNzhcdWM3NzQgXHVjMjE4XHVjNWY0XHViNGU0XHVjNzc0IFx1YWMxMFx1YzE4Y1x1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViMDk4XHVkMGMwXHViMDljXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJkODRcdWQ1NzRcdWI0MWMgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmFhOVx1YWM3OFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWI0ZTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWJhYTlcdWFjNzhcdWM3NzQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YmQ5OVx1YzYwMFx1Yzc0NCBcdWI1NGMgXHViYWE5XHVhYzc4XHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgMTExMDExMTEwMTFcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0MCAoMTExKSgwMTExMSkoMDExKVx1Yjg1YyBcdWJkODRcdWQ1NzRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWNiZFx1YzZiMCBcdWFjMDFcdWFjMDFcdWM3NzQgXHViYWE5XHVhYzc4XHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc4NFx1Yzc0MCBcdWM3OTBcdWJhODVcdWQ1NThcdWFjZTAsIDExMSAmZ3Q7IDAxMTExICZndDsgMDExXHVjNzc0IFx1YzEzMVx1YjliZFx1ZDU1OFx1YmE3MCwgMTExMDExMTFcdWFjZmMgMDExMTEwMTExIFx1YzkxMSBcdWM1YjRcdWIyOTAgXHVhYzgzXHViM2M0IFx1YmFhOVx1YWM3OFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNTQ0XHViMmM4XHViYmMwXHViODVjIFx1YzcwNFx1Yzc1OCBcdWI0NTAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWM2MDhcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD4wXHVhY2ZjIDFcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3MDRcdWM3NTggXHViNDUwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIzYzRcdWI4NWQgXHViYWE5XHVhYzc4XHVjNzc0IFx1YzIxOFx1YzVmNFx1YjRlNFx1Yjg1YyBcdWJkODRcdWQ1NzRcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2MzZVx1YzU0NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM1ZjQgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YjMwMFx1YzE4YyBcdWFkMDBcdWFjYzRcdWIyOTQgXHVjMGFjXHVjODA0XHVjMmRkIFx1YzIxY1x1YzExY1x1Yjg1YyBcdWM4MTVcdWM3NThcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgQSAmbHQ7IEJcdWM3NTggXHVhZDAwXHVhY2M0XHVhYzAwIFx1YzEzMVx1YjliZFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgQSBcdWI0YTRcdWM1ZDAgXHViYTg3IFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWJkOTlcdWM3NzRcdWJhNzQgQlx1YWMwMCBcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMDk4LCBBXHVjNjQwIEJcdWFjMDAgXHVjNTVlXHVjNzU4IFx1YmE4NyBcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YWMxOVx1YWNlMCBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzIyYlx1Yzc5MFx1YjI5NCBCXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViMzU0IFx1ZDA3MCBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgMDAxICZsdDsgMDAxMCwgMTEwMTAxMSAmbHQ7IDExMDExMDAwXHVjNzc0IFx1YzEzMVx1YjliZFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHVjOWM0XHVjMjE4XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWM1NDRcdWIyZDhcdWM1ZDAgXHVjOGZjXHVjNzU4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IDBcdWFjZmMgMVx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMjE4XHVjNWY0XHVjNzQwIFx1YWNmNVx1YmMzMSBcdWM1YzZcdWM3NzQgXHViZDk5XHVjNWI0XHVjMTFjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVhZGY4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxXHVjNzc0XHVjMGMxIDEwMFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmFhOVx1YWM3OFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWI4NWMgXHViZDg0XHVkNTc0XHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmFhOVx1YWM3OFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVhZDA0XHVkNjM4XHViODVjIFx1YmIzNlx1YzViNFx1YzExYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjA3MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik5lY2tsYWNlIERlY29tcG9zaXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBzZXQgb2YgY3ljbGljIHJvdGF0aW9ucyBvZiBhIHN0cmluZyBhcmUgdGhlIHN0cmluZ3Mgb2J0YWluZWQgYnkgZW1iZWRkaW5nIHRoZSBzdHJpbmcgY2xvY2t3aXNlIG9uIGEgcmluZywgd2l0aCB0aGUgZmlyc3QgY2hhcmFjdGVyIGZvbGxvd2luZyBvbiB0aGUgbGFzdCwgc3RhcnRpbmcgYXQgYW55IGNoYXJhY3RlciBwb3NpdGlvbiBhbmQgbW92aW5nIGNsb2Nrd2lzZSBvbiB0aGUgcmluZyB1bnRpbCB0aGUgY2hhcmFjdGVyIHByZWNlZWRpbmcgdGhlIHN0YXJ0aW5nIGNoYXJhY3RlciBpcyByZWFjaGVkLiBBIHN0cmluZyBpcyBhIG5lY2tsYWNlIGlmIGl0IGlzIHRoZSBsZXhpY29ncmFwaGljYWxseSBzbWFsbGVzdCBhbW9uZyBhbGwgaXRzIGN5Y2xpYyByb3RhdGlvbnMuIEZvciBpbnN0YW5jZSwgZm9yIHRoZSBzdHJpbmcgMDEwMTEgdGhlIGN5Y2xpYyByb3RhdGlvbnMgYXJlICgxMDExMCwwMTEwMSwxMTAxMCwxMDEwMSwwMTAxMSksIGFuZCBmdXJ0aGVybW9yZSAwMTAxMSBpcyB0aGUgc21hbGxlc3Qgc3RyaW5nIGFuZCBoZW5jZSwgYSBuZWNrbGFjZS48XC9wPlxyXG5cclxuPHA+QW55IHN0cmluZyBTIGNhbiBiZSB3cml0dGVuIGluIGEgdW5pcXVlIHdheSBhcyBhIGNvbmNhdGVuYXRpb24gUyA9IFQxVDIuLi5UayBvZiBuZWNrbGFjZXMgVGkgc3VjaCB0aGF0IFRpKzEgJmx0OyBUaSBmb3IgYWxsIGkgPSAxLC4uLiAsIGsgJm1pbnVzOyAxLCBhbmQgVGlUaSsxIGlzIG5vdCBhIG5lY2tsYWNlIGZvciBhbnkgaSA9IDEsLi4uICwgayAmbWludXM7IDEuIFRoaXMgcmVwcmVzZW50YXRpb24gaXMgY2FsbGVkIHRoZSBuZWNrbGFjZSBkZWNvbXBvc2l0aW9uIG9mIHRoZSBzdHJpbmcgUywgYW5kIHlvdXIgdGFzayBpcyB0byBmaW5kIGl0LjxcL3A+XHJcblxyXG48cD5UaGUgcmVsYXRpb24gJmx0OyBvbiB0d28gc3RyaW5ncyBpcyB0aGUgbGV4aWNvZ3JhcGhpY2FsIG9yZGVyIGFuZCBoYXMgdGhlIHVzdWFsIGludGVycHJldGF0aW9uOiBBICZsdDsgQiBpZiBBIGlzIGEgcHJvcGVyIHByZWZpeCBvZiBCIG9yIGlmIEEgaXMgZXF1YWwgdG8gQiBpbiB0aGUgZmlyc3QgaiAmbWludXM7IDEgcG9zaXRpb25zIGJ1dCBzbWFsbGVyIGluIHRoZSBqdGggcG9zaXRpb24gZm9yIHNvbWUgai4gRm9yIGluc3RhbmNlLCAwMDEgJmx0OyAwMDEwIGFuZCAxMTAxMDExICZsdDsgMTEwMTEwMC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBpcyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIG4sIHRlbGxpbmcgdGhlIG51bWJlciBvZiB0ZXN0IHNjZW5hcmlvcyB0byBmb2xsb3cuIEVhY2ggc2NlbmFyaW8gY29uc2lzdHMgb2Ygb25lIGxpbmUgY29udGFpbmluZyBhIG5vbi1lbXB0eSBzdHJpbmcgb2YgemVyb3MgYW5kIG9uZXMgb2YgbGVuZ3RoIGF0IG1vc3QgMTAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHNjZW5hcmlvLCBvdXRwdXQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgbmVja2xhY2UgZGVjb21wb3NpdGlvbiBvZiB0aGUgc3RyaW5nLiBUaGUgbmVja2xhY2VzIHNob3VsZCBiZSB3cml0dGVuIGFzICZyc3F1bzsoJnJzcXVvOyBuZWNrbGFjZSAmcnNxdW87KSZyc3F1bzsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==