목걸이 수열
시간 제한2초메모리 제한128 MB
이진 문자열을 사전순으로 엄격히 감소하면서 인접한 두 조각을 합치면 목걸이 수열이 되지 않도록 목걸이 수열들로 분해합니다.
문제
0과 1로 이루어진 수열은 원형으로 돌려 볼 수 있다. 어떤 수열이 자기 자신을 포함한 모든 회전 결과보다 사전식으로 작거나 같으면, 그 수열을 목걸이 수열이라고 부른다. 01011은 회전 결과 10110, 01101, 11010, 10101, 01011 중 사전식으로 가장 작으므로 목걸이 수열이다.
0과 1로 이루어진 수열 S가 주어진다. S를 여러 개의 목걸이 수열로 나누되, 다음 두 조건을 만족해야 한다.
- 나누어진 목걸이 수열들은 왼쪽부터 오른쪽으로 사전식 엄격한 내림차순이다.
- 서로 이웃한 두 목걸이 수열을 이어 붙인 문자열은 목걸이 수열이 아니다.
주어진 수열을 위 조건에 맞게 나눈 결과를 출력하는 프로그램을 작성하라.
두 수열의 대소 관계는 사전식 순서로 정한다. A 뒤에 문자를 하나 이상 붙여 B가 되면 A < B이다. 또는 두 수열이 앞부분은 같고 처음으로 달라지는 위치에서 B의 문자가 더 크면 A < B이다. 따라서 001 < 0010, 1101011 < 11011000이 성립한다. 이 관계는 이진수의 크기 비교가 아니다.
입력
첫째 줄에 0과 1로 이루어진 수열 S가 공백 없이 주어진다. S의 길이는 1 이상 100 이하이다.
출력
첫째 줄에 조건을 만족하는 분해 결과를 출력한다. 각 목걸이 수열은 괄호로 감싸서 이어 출력한다.