3068 : 피카띠용소
- 제한시간
- 1000 ms
- 메모리제한
- 128 MB
- 해결횟수
- 33 회
- 시도횟수
- 230 회
문제
피카띠용소는 유명한 띠 그림의 대가이다.
얇은 폭의 띠에 그림을 그리는 피카띠용소는 나름대로 규칙을 가지고 그린다.
규칙은 다음과 같다.
1. 먼저 한 번의 붓 칠로 폭이 다 덥힐 정도의 얇은 폭의 띠를 N등분한다.
2. 왼쪽에서 오른쪽으로 진행하면서 원하는 연속한 셀들을 선택하여 한 가지 색을 칠한다.
칠 할 때는 연속된 셀을 한 번에 칠한다.
계속 오른쪽으로 진행하면서 원하는 연속한 셀들을 선택하여 다른 색을 칠한다.
띠의 오른쪽 끝까지 왔다면 멈추고 색이 마르기를 기다린다. 2번 작업을 하나의 라운드라고 한다.
3. 띠의 색이 다 마르면 2번 작업을 시행하기를 원하는 만큼 한다.
물론 원하지 않는다면 하지 않을 수도 있다.즉 여러 라운드를 시행할 수 있다.
이미 칠해진 색 위에 새로운 색을 덧칠할 수도 있다.
4. 색을 칠할 때 한번 사용한 색은 다시 사용하지 않는다.
예를 들어 길이 7짜리 띠를 7등분 하였다고 하자.
1라운드 : 2번에서 5번까지 1번 색을 칠한다.
6번에서 7번까지 3번 색을 칠한다.
마르기를 기다린 후
2라운드 : 3번에서 3번까지 4번 색을 칠한다.
4번에서 4번까지 5번 색을 칠한다.
따라서 입출력 예는 두 번의 라운드로 그려진 그림이다.
그림을 모사하여 판매하는 피짝퉁소가 화가 피카띠용소의 작품을 모사할 계획이다.
그런데 정통한 소식통에 따르면 피카띠용소는 최소의 라운드로 그림을 그린다고 한다.
완성된 피카띠용소의 그림을 분석하여 최소 몇 라운드 만에 그림이 완성되었는지 알아내는 프로그램을 작성하시오.
입력형식
출력형식
입력 예7 0 1 4 5 1 3 3 |
출력 예2 |