2070번 - 목걸이 수열 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 101 | 31 | 28 | 41.791% |
문제
어떤 수열이 주어졌을 때, 이 수열을 회전하면 여러 가지 수열을 얻을 수 있다. 이와 같이 수열을 회전하면서 얻은 수열들이 모두 원래의 수열보다 같거나 크면, 원래의 수열을 목걸이 수열이라 부른다. 예를 들어 01011은 목걸이 수열인데, 이는 10110, 01101, 11010, 10101, 01011 중에서 제일 작은 것이 원래의 01011이기 때문이다.
0과 1로 구성된 수열 S가 주어졌을 때, 이를 목걸이 수열들로 분해할 수 있다. 가장 간단한 방법은 각각의 숫자 단위로 분해하는 것인데, 그 외에도 다음의 조건을 만족하도록 분해할 수도 있다.
- 분해된 각각의 목걸이 수열들이 감소하는 순서대로 나타난다.
- 분해된 각각의 목걸이 수열들에 대해서, 인접한 두 개의 목걸이 수열을 붙였을 때 목걸이 수열을 이루지 않는다.
예를 들어 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)
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호