시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 38 | 7 | 7 | 30.435% |
상근이는 몇 달전에 대박의 꿈을 안고 아이폰 앱의 세계에 발을 들였다. 상근이는 게임을 하나 만들었는데, 이 게임에는 전체 사용자의 순위를 보여주는 기능이 있다. 상근이는 점수를 내림차순으로 정렬해 사용자의 순위를 보여주려고 한다.
사용자의 점수를 저장하는데 사용한 자료구조는 오직 연산 하나만 수행할 수 있다. 이 연산은 i번째 사용자를 j번째로 옮기는데, 다른 사용자의 상대적인 순서를 바꾸지 않는다.
예를 들어, i>j인 경우에 j와 i-1번 사이의 사용자의 순위는 1씩 증가한다. 반대로 i<j인 경우에는 i+1과 j 사이의 사용자의 순위가 1씩 감소한다.
연산을 한 번 사용할 때, 이동시킬 사용자를 찾는데 i단계, 이동할 위치를 찾는데 j단계가 필요하기 때문에, i번째 사용자를 j번째로 옮기는데 드는 비용은 i+j이다. 순위는 1부터 시작한다.
현재 자료구조에 저장된 점수가 주어졌을 때, 사용자를 내림차순으로 정렬하기 위해 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.
첫째 줄에 저장된 점수의 수 n (2 ≤ n ≤ 1000) 이 주어진다. 다음 줄에는 점수 si가 현재 자료구조에 저장되어 있는 순서대로 주어진다. (0 ≤ si ≤ 1,000,000) 두 점수가 같은 경우는 없다.
첫째 줄에 점수를 내림차순으로 정렬하기 위해 필요한 이동 횟수를 출력한다. 다음 줄에는 각 이동을 순서대로 출력한다. i번째 점수를 j번째로 옮긴 경우에는 i j를 출력한다.
5 20 30 5 15 10
2 2 1 3 5