JOI 2012/2013 본선 5- 버블정렬(고) > 문제은행 : 정보올림피아드&알고리즘




2737 : 버블정렬(고)

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

문제

GodJail(갓재일)은 정렬을 할 줄 모르는 불쌍한 어린 양들을 위해 길이가 N인 수열 A를 정렬하는 함수를 아래와 같이 만들어줬다.

여기서 swap(x, y) 함수는 x, y의 값을 서로 바꾸는 함수이다.

 

 

 

그런데, N이 커지면 swap 함수를 호출하는 횟수가 많아져 정렬하는 데 걸리는 시간이 급격하게 늘어나기 때문에 어린 양들이 곤혹을 치르고 있다.

 

그러다가 태영이라는 이름의 어린 양이 'bubble_sort 함수를 호출하기 전에

swap(A[x], A[y]) (단, 0 ≤ x < y ≤ N-1) 함수를 한 번 호출하면 정렬하는 데 걸리는 시간이 많이 줄어들지 않을까?' 라는 의문을 제시하였다.

 

태영이의 등장에 따라 다른 양들이 혼란을 많이 겪고 있다. 

GodJail의 제자인 당신이 'swap 함수를 호출하는 횟수의 최솟값'을 구해서 불쌍한 어린 양들에게 태영이의 아이디어가 틀렸다는 것을 알려주자.


입력형식

첫 번째 줄에는 A의 원소의 수 N이 주어진다. (2 ≤ N ≤ 100,000) 두 번째 줄에는 A[i]가 주어진다. (1 ≤ A[i] ≤ 1,000,000,000) 전체 데이터의 10%는 N ≤ 1,000이며, 전체 데이터의 30%는 N ≤ 3,000이다. 전체 데이터의 80%는 A의 모든 원소의 값이 서로 다르다.

출력형식

bubble_sort 함수 안에서 swap 함수를 호출하는 횟수의 최솟값을 출력한다. bubble_sort 함수를 호출하기 전에 반드시 swap(A[x], A[y])를 호출해야 함에 유의하여라.

입력 예

5
3 1 7 9 5

출력 예

2

입력 예

5
10 3 6 8 1

출력 예

0

입력 예

3
1 2 3

출력 예

1

Hint!

예제 1 : swap(A[0], A[1])를 호출하면 된다. 예제 2 : swap(A[0], A[4])을 호출하면 된다. 예제 3 : swap(A[0], A[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