[백준 10090] Counting Inversion C++

10090번: Counting Inversions

분할 정복

---

1. 문제해결 아이디어

임의의 수열에서 자신보다 뒤에 있는데 자신보다 작은 수의 개수의 총 합을 구하는 문제이다

N^2로 풀면 너무 쉽겠지만 N <= 1000000이므로 불가능하다.

이전에 버블 소트_1517 문제를 푼 경험이 있어서 병합 정렬 과정을 직접 손으로 그려가며 계산해보니까

구현에 대한 감이 바로왔다

 

*병합정렬 과정에서 arr[lo]와 arr[hi]를 비교했을 때 arr[hi]가 더 작다는 말은

arr[lo~mid]까지의 모든 원소가 arr[hi]보다 크다는 말이다

 

Ex) 4 7 / 1 2 3 처럼 나누어져 있을 때

 

1. arr[lo] = 4이고 arr[hi] = 1이다

arr[hi]가 더 작으므로 lo(0)~mid(1)까지의 거리(mid-lo+1) (2) 만큼 Inv에 더해준다

그리고 hi++를 해서 오른쪽 배열의 두 번째 원소로 index를 옮겨준다

2. arr[lo] = 4, arr[hi] = 2 이다

위와 동일하게 Inv에 2를 더해주고 hi++해준다

3... 반대의 경우는 Inv에 더해주는 작업을 안해주면 됨

그리고 while문을 돌면서 temparr에 저장해 놓았던 정렬된 배열을 가지고

for문에서 arr배열에 업데이트해주는 작업을 하면 끝

---

2. 코드

 

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 51 52 53 54 55

#include <iostream> #include <vector>   using namespace std;   vector<int> arr, temparr;   int N; long long Inv = 0;   void counting_inversions(int st, int ed){     if(st == ed) return;          int mid = (st + ed)/2;          counting_inversions(st, mid);     counting_inversions(mid+1, ed);          int lo = st;     int hi = mid+1;     long long temp_Inv = 0;     int idx = 0;          while(lo <= mid || hi <= ed){         if(lo <= mid && (hi > ed || arr[lo] < arr[hi])){             temparr[idx++] = arr[lo++];         }         else{             temparr[idx++] = arr[hi++];             temp_Inv += (mid - lo + 1);         }     }          for(int i = st; i <= ed; i++){         arr[i] = temparr[i - st];     }     Inv += temp_Inv;      }   int main(){     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);     cin >> N;     arr.resize(N+1);     temparr.resize(N+1);     for(int i = 0; i < N; i++){         cin >> arr[i];     }          counting_inversions(0, N-1);          cout << Inv;          return 0; } Colored by Color Scripter

cs