문제
매일 매일 새로운 복잡한 소재를 공부해야하는 불쌍한 알고리즘 수강생들에게 익숙한 소재를 선사한다.
바로 삽입 정렬이다. 삽입 정렬은 대부분 알고 있겠지만, 모르는 사람들을 위해 예시를 하나 들어보자.
배열 arr이 [4, 2, 3, 1]이고, 이것을 정렬하고자 한다.
[4, 2, 3, 1] //4가 삽입되면서 첫 번째 자리를 지킨다.
[2, 4, 3, 1] //2가 삽입되면서, 4를 밀어내고 첫 번째 자리로 이동한다.
[2, 3, 4, 1] //3이 삽입되면서 4를 밀어내고 두 번째 자리로 이동한다.
[1, 2, 3, 4] //1이 삽입되면서 4, 3, 2를 각각 밀어내고 첫째 자리로 간다.
총 교환(밀어내기)수: 1+1+3 = 5
배열이 주어질 때 그 배열을 삽입 정렬할때의 교환(밀어내기)의 수의 총합을 구하여라.
입력
첫 줄에 정수 t가 주어진다. t는 테스트케이스의 개수다.
각 테스트케이스별로 두 줄이 주어진다.
첫 줄은 배열의 크기인 정수 n이다.
두 번째 줄은 정렬하고자 하는 n개의 배열의 원소 ai가 공백을 사이에 두고 주어진다.
제약 형식
테스트케이스의 개수 t에 대해서, 1≤t≤15 를 만족한다.
모든 부분문제에 있어서 1≤n≤100,000, 1≤ai≤109를 만족한다.
출력
t줄에 걸쳐, 각 배열을 삽입 정렬할 때 일어나는 총 교환(밀어내기)의 수를 구하여 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 1점 | n=100,000이고 ai = 2×i-1을 만족한다. |
| #2 | 5점 | 모든 ai는 다른 값이고, 배열은 내림차순 정렬되어 들어온다. |
| #3 | 11점 | n≤5,000를 만족한다. |
| #4 | 83점 | 주어진 제약조건 외에 아무 제약조건이 없다. |
예제
2
5
1 1 1 2 2
5
2 1 3 1 2
0
4
로그인해야 코드를 작성할 수 있어요.