cow sorting > 문제은행

본문 바로가기


실전대비 Level5

1424 : cow sorting

제한시간: 2000 ms    메모리제한: 64 MB
해결횟수: 27 회    시도횟수: 245 회   



어느 날 저녁, 농부 창호의 N(1≤N≤10,000)마리 소들은 우유를 짜기 위해서 줄서있다. 각각의 소들은 1이상 100,000까지의 서로 다른 뺀질거림 수치를 가지고 있다.

 

말을 잘 듣지 않는 소가 농부 창호의 우유짜는 기구를 망가뜨릴 확률이 좀 더 높기 때문에, 농부 철기는 소들을 뺀질거림 수치가 낮은 소부터 높은 순으로 새로이 줄을 세우려고 한다.

 

이 새로운 줄을 세우는 작업동안, 어떠한 임의의 두 소는 (꼭 인접해있지 않아도) 서로 교체될 수 있다.

 

X와 Y를 각각 교체하려는 소의 말안들음 수치라고 할 때, 말을 듣지 않는 소일수록 소의 자리를 움직이는 것도 좀 더 힘들기 때문에 농부 창호가 두 소를 교체하는데엔 X+Y의 시간이 걸린다.

 

소를 새로이 배열시키는 일에 필요한 최소의 시간을 계산해서 농부 창호를 도와주어라.


첫 번째 줄에는 한 개의 정수 N이 입력된다.
두 번째 줄부터 N+1번째 줄에는 하나의 정수가 쓰여 있으며, i+1번째 줄에에 위치한 정수는 i번째 소의 뺀질거림 수치를 뜻한다.


소들을 뺀질거림 수치를 기준으로 재 정렬하는데 드는 최소한의 시간을 출력하라.

[Copy]
3 
2 
3 
1
[Copy]
7





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.