백준 10090(Counting Inversions)

https://www.acmicpc.net/problem/10090

10090번: Counting Inversions

 

어떤 수열이 주어졌을때에, 배열이 역순으로 존재하는 크기 2의 부분수열 갯수를 구하는 문제. 

 

분할정복에서 배우는 중이라서 분할정복으로 접근하면, 쪼개고, 계산한다. 

 

쪼개는 방법을 생각할 때에는 

 

그 방법을 사용했을때에 정답을 구할 수 있는지 생각하는 것이 중요하다. 

 

위의 문제에서는 

 

부분문제들의 합이 정답인 것을 확인 할 수 있다. 

 

중복되는 경우도 없고, 빠뜨리는 경우도 없다.

 

그렇다면 이제 계산하는 방법을 생각해보자

계산은 정렬된 상태에서 계산하는 것이 좋다. 

 

왜냐하면 정렬되지 않은 상태라면 O(N^2) 이 되고, N = 10^6이므로 시간초과의 위험이 존재한다.

 

그러므로, 정렬하고, 계산을 한다. 

 

1 3 4 6 / 3 4 7 9

 

왼쪽 배열과 오른쪽 배열의 각각의 인덱스 포인터를 설정해서, 왼쪽이 더 큰 경우(문제의 조건에 만족)에는 오른쪽의 포인터를 움직인다. 

 

오른쪽이 큰 경우에는 이전까지의 오른쪽 포인터를 이용해서 왼쪽 특정 인덱스는 총 몇개가 더 큰 수인지 찾는다. 

 

위 과정을 반복해서 하나의 포인터가 먼저 끝나면 

 

이제 남은 포인터를 끝까지 밀면서 계산한다.

 

만약에 왼쪽이 남으면 왼쪽은 갯수 계산이 안 된것이므로 오른쪽 포인터를 이용해서 갯수를 계산한다.

 

오른쪽은 그냥 ++하면서 합치기 위해서 계산 

 

시간복잡도는 쪼개는거 logn 계산하는거 n해서 

 

O(nlogn)이라고 하는 것 같은데, 솔직히 아직까지 직관적으로 딱 떨어지지는 않는다. 

 

#include<iostream>
using namespace std;
#define MAX 1000001

int arr[MAX];
int tmp[MAX];
int N;
long long int sum;


void solve(int l, int r) {
	if (l == r) return;
	int m = (r + l) / 2;

	solve(l, m);
	solve(m + 1, r);
	
	int lp = l;
	int rp = m + 1;
	int idx = l;
	while (lp <= m && rp <= r) {
		if (arr[lp] > arr[rp]) {
			tmp[idx++] = arr[rp++];
		}
		else {
			sum += rp - m - 1;
			tmp[idx++] = arr[lp++];
		}
	}
	while (lp <= m) {
		sum += rp - m - 1;
		tmp[idx++] = arr[lp++];
	}
	while (rp <= r) {
		tmp[idx++] = arr[rp++];
	}
	for (int i = l; i <= r; i++)arr[i] = tmp[i];
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	solve(0, N - 1);
	cout << sum << "\n";
}