USACO 2019 January Contest, Bronze- Sleepy Cow Sorting > 문제은행 : 정보올림피아드&알고리즘




3537 : Sleepy Cow Sorting

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

문제

퐐머 도훈을 따라 N마리의 소들이 일렬로 걷고 있다.

하루종일 여기저기서 풀을 뜯은 소들은 헛간으로 돌아가는 길이 졸립고 지루하다.

소들의 목에는 고유번호가 부착되어 있는데 돌아가는 길에 앞서거니 뒷서거니 하며 순서가 섞였다.

 

헛간으로 돌아가다 잠시 쉬면서 소들을 확인하던 도훈이는 번호에 맞게 오름차순으로 소들을 정렬하고 싶어졌다.

도훈이는 다음과 같은 방법으로 소들을 정렬한다.

도훈이는 뒤돌아서서 도훈이 바로 뒤에 있던 소에게 K칸 뒤로 가라고 명령한다.

 

예를 들어 도훈이와 4마리의 소들이 아래와같이 서있다고 하자.

도훈, 4, 3, 2, 1

 

이제 도훈이는 4번 소에게 2칸 뒤로 가라고 명령하면

도훈, 3, 2, 4, 1 이 된다.

 

이제 도훈이는 3에게만 명령을 내릴 수 있다.

 

소들이 서있는 정보가 주어지고 고유번호의 오름차순으로 정렬하려고 할 때,

도훈이의 최소명령수를 구하는 프로그램을 작성하시오.

 


입력형식

첫 행에 소들의 수 N(1 <= N <= 100)이 첫 행에 입력된다. 두 번째 행에 N마리의 소들의 고유번호가 공백으로 구분되어 주어진다.

출력형식

소들을 고유번호의 오름차순으로 정렬할 때 도훈이가 하는 명령수의 최소값을 출력한다.

입력 예

4
1 2 4 3

출력 예

3


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