[SwExpertAcademy] Inversion Counting

문제 출처 :

https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxyRM6AhMDFAW4

알고리즘 분석 :

문제 해결에 필요한 사항

1. Merge Sort

i < j 인데 A[i] > A[j] 이 말은 병합 정렬의 핵심을 의미하고 있다.

즉, 이 문제는 병합 정렬을 제대로 이해하고 있다면 해결 할 수 있는 문제이다.

병합 정렬에서 오른쪽에 있는 것과 왼쪽에 있는 것 중 arr[left] < arr[right]라는 조건에 의해 

만약 오른쪽의 것이 먼저 정렬 대상이 된다면 결국 현재 남은 왼쪽 것들이 오른쪽 것보다 크다는 의미가 되므로

swap될 것들은 mid - left + 1개가 된다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

#include <iostream>   int arr[100002]; int tmp[100002]; long long ans;   void mergeSort(int start, int end) {     if (start < end) {           int mid = (start + end) >> 1;         mergeSort(start, mid);         mergeSort(mid + 1, end);           int left = start, right = mid + 1;         int idx = start;                    while (left <= mid || right <= end) {             if (right > end || (left <= mid && arr[left] < arr[right])) {                   tmp[idx++] = arr[left++];             }             else {                 ans += (mid - left + 1);                 tmp[idx++] = arr[right++];             }         }         for (int i = start; i <= end; i++)             arr[i] = tmp[i];     } } int main() {     int tCase;     scanf("%d", &tCase);       for (int tc = 1; tc <= tCase; tc++) {         ans = 0;         int n;         scanf("%d", &n);           for (int i = 0; i < n; i++)         {             scanf("%d", &arr[i]);         }         mergeSort(0, n - 1);           printf("#%d %lld\n", tc, ans);     }     return 0; } Colored by Color Scripter

cs