USACO 2017 US Open Gold 3. Modern Art 2- 피카띠용소 > 문제은행 : 정보올림피아드&알고리즘




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번 색을 칠한다.

 

 

따라서 입출력 예는 두 번의 라운드로 그려진 그림이다.

그림을 모사하여 판매하는 피짝퉁소가 화가 피카띠용​소의 작품을 모사할 계획이다. 

그런데 정통한 소식통에 따르면 피카띠용​소는 최소의 라운드로 그림을 그린다고 한다.

 

완성된 피카띠용​소의 그림을 분석하여 최소 몇 라운드 만에 그림이 완성되었는지 알아내는 프로그램을 작성하시오. 


입력형식

첫 행에 띠의 길이 N(1 <= N <= 100,000)이 입력된다. 이후 N개의 행에 N등분한 각 셀에 칠해진 색의 번호 Ci 입력된다. (1 <= Ci <= 100,000) 당연한 일이겠지만 피카띠용소는 아무색도 칠하지 않은 백지를 작품으로 내지는 않는다.

출력형식

피카띠용소가 색을 칠하는데 사용한 최소 라운드 수를 출력한다. 만일 입력데이터가 피카띠용소의 작품이 아닌경우 -1을 출력한다.

입력 예

7
0
1
4
5
1
3
3

출력 예

2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP