[백준 10090] Counting Inversions

문제 링크 => 10090번: Counting Inversions (acmicpc.net)

10090번: Counting Inversions

---

A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once.

Two integers in а permutation form an inversion, when the bigger one is before the smaller one.

Write program invcnt that computes the number of the inversions in a given permutation.

 

분할정복을 이용한 Merge sort 문제이다.

 

Brute Force로 문제를 접근하기에는 n값이 1,000,000 이라는 점과 O(N^2) 으로 인한 시간 제한이 발생할 수 있다. 

 

따라서 이를 해결하기 위해 O(NlogN) 인 Merge Sort를 이용해야 한다. 

 

따라서 배열들을 반으로 나눠서 해결할 때, 왼쪽 배열의 index는 오른쪽 배열의 index보다 작다는 것이 확실하므로 이를 통해서 각 배열들을 정렬하는 과정에서 inverse counting 이 가능하다.

 

inverse counting 을 구하는 방법을 다음과 같은 예시를 통하 알아보도록 하자.

 

(1) [5, 6, 7] [1, 2, 3, 4]

이 때 [1, 2, 3, 4]는 [5, 6, 7]보다 작으므로 총 4+4+4=12 개이다.

 

(2) [3, 5, 7] [1, 2, 4, 6]

이때 [1, 2]는 [3, 5, 7]보다 작고 [4]는 [5, 7]보다 작고 [6]는 [7]보다 작으므로 총 3+3+2+1=9 개이다.

 

(3) [2, 4, 7] [1, 3, 5, 6]

이때 [1]은 [2, 4, 7]보다 작고 [3]는 [4, 7]보다 작고  [5, 6]는 [7]보다 작으므로 총 3+2+1+1=7 개이다.

 

Merge Sort를 진행하면서 Inverse 일때 더하는 과정을 살펴보면 left배열의 원소가 right배열의 원소보다 큰 경우에 대해서 cnt += (left 배열의 size - left index) 를 한다는 것을 알 수 있다.

 

따라서 모든 배열들을 2개의 배열로 분할하여 사이즈가 2 이상부터 시작해서 사이즈 n 까지 차근차근 Merge Sort를 해주면서 Inverse 일 때의 counting은 위의 방법을 통하여 구하면 끝이다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int n;

ll merge_Sort(vector<int> v1, vector<int> v2, vector<int>& v) {
	ll cnt = 0;
	int left = 0, right = 0;

	for (int i = 0; i < v.size(); i++) {
		if (left == v1.size()) {
			int size = v2.size();
			while (right < size) {
				v[i++] = v2[right++];
			}
		}
		else if (right == v2.size()) {
			int size = v1.size();
			while (left < size) {
				v[i++] = v1[left++];
			}
		}
		else {
			if (v1[left] > v2[right]) {
				v[i] = v2[right++]; 
				cnt += (ll)(v1.size() - left);
			}
			else {
				v[i] = v1[left++];
			}
		}
	}

	return cnt;
}

ll inv_Count(vector<int>& v) {
	if (v.size()==1) return 0;

	vector<int> v1, v2;
	for (int i = 0; i < v.size() / 2; i++) v1.push_back(v[i]);
	for (int i = v.size() / 2; i < v.size(); i++) v2.push_back(v[i]);
	
	ll result = inv_Count(v1) + inv_Count(v2);

	return result = result + merge_Sort(v1, v2, v);
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	vector<int> v;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		v.push_back(x);
	}
	cout << inv_Count(v);
	
	return 0;
}