백준 BOJ 7578 - 공장

inversion counting 연습 문제

사실 코이앞두고 이게 뭐하는짓인가 싶긴한데

몰?루

 

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

7578번: 공장

교차하는 케이블을 하나 풀어내는데 필요한 연산이

버블소트에서의 swap 연산과 같고,

버블소트에서의 swap 연산 횟수는 inversion 의 갯수와 같기 때문에

이 문제는 inversion counting 으로 볼수 있게 된다.

목적하고자 하는 결과값이 정렬된 쌍이 아니기 때문에

입력된 숫자 a1 a2 a3 a4 a5를 숫자로보기보단

문자열로 보듯이 해서

다른 숫자로 바꿔줘야함.

편의상 map을 사용했다.

 

#include <bits/stdc++.h>
using namespace std;

map<int,int> m;

int arr[567890] = {0};
int tmp[567890] = {0};

long long int ans = 0;

void merge(int s, int mid, int e){
	int ptr = s;
	int s1  = s;
	int s2  = mid+1;
	
	while(s1<=mid && s2<=e){
		if(arr[s1] <= arr[s2]) tmp[ptr++] = arr[s1++];
		else                 { tmp[ptr++] = arr[s2++]; ans += (mid-s1+1); }
	}
	if(s1<=mid) for(int i=s1; i<=mid; i++) tmp[ptr++] = arr[i];
	else        for(int i=s2; i<=e;   i++) tmp[ptr++] = arr[i];
	
	for(int i=s; i<=e; i++) arr[i] = tmp[i];
	return;
}

void mergesort(int s, int e){
	if(s<e){
		int mid = (s+e)/2;
		mergesort(s,mid);
		mergesort(mid+1,e);
		merge(s,mid,e);
	}
	return;
}

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	
	int n,tmp;
	cin >> n;
	for(int i=1; i<=n; i++)  cin >> arr[i];
	for(int i=1; i<=n; i++){ cin >> tmp; m[tmp] = i; }
	for(int i=1; i<=n; i++)  arr[i] = m[arr[i]];
	
	mergesort(1,n);
	
	//for(int i=1; i<=n; i++) printf("%d ", arr[i]);
	
	cout << ans;
	return 0;
}

N이 50만으로 상당히 크기 때문에

역순으로 정렬된 값이 들어오면

int범위를 넘는다.

정답은 long long 형으로 저장해야함에 유의할것.