KOI 2차 2020 고2- 순서 섞기 > 문제은행 : 정보올림피아드&알고리즘




4607 : 순서 섞기

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
0 회   
시도횟수
0 회   

문제

정수가 저장된 크기 N인 배열 A가 있을 때, ‘순서 섞기’ 연산은 아래와 같이 정의된다.

 

1. 크기가 N인 배열 B를 이용하여, 배열 A의 좌측 끝 또는 우측 끝에 있는 값 중 하나를 차례로 꺼내어 배열 B에 좌측부터 순서대로 저장한다. 아래의 그림에서 값이 꺼내지는 순서는 9, 34, 19, 12, 25, 4, 5, 36이다.

 

2. 배열 B를 배열 A에 복사한다.

 

 

위에서 보인 그림처럼 순서 섞기 연산을 하면 배열 A의 값은 다음과 같이 변경된다.

 

(34, 19, 5, 36, 4, 25, 12, 9) ⇒ (9, 34, 19, 12, 25, 4, 5, 36)

 

배열 A의 i번째 원소를 Ai라고 나타내자. “1 ≤ i < j ≤ N이면 Ai ≤ Aj이다.”가 성립할 때, “배열 A는 단조증가한다”라고 말한다.

 

정수가 저장된 크기 N인 배열 A가 주어질 때, 배열 A가 단조증가하도록 정렬하기 위해 필요한 ‘순서 섞기’ 연산의 최소 횟수를 계산하는 프로그램을 작성하시오.


 


제약 조건


  • 1 ≤ N ≤ 300,000
  • 1 ≤ Ai ≤ 109

 

부분문제


  1. (4점) N ≤ 8.
  2. (9점) 답이 2 이하.
  3. (22점) Ai ≤ 2.
  4. (18점) 모든 Ai가 서로 다름.
  5. (47점) 추가 제약 조건 없음.​

입력형식

첫 번째 줄에 정수 N이 주어진다.

두 번째 줄에 배열 A에 저장된 N개의 정수 A1, ..., AN이 공백을 사이에 두고 차례대로 주어진다.​ 


출력형식

배열 A가 단조증가하도록 정렬하기 위해 필요한 ‘순서 섞기’ 연산의 최소 횟수를 출력한다. 


입력 예

3
2 2 5

출력 예


입력 예

6
1 5 8 10 3 2

출력 예

1


경기도 안양시 동안구 평촌대로 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