[ BOJ 백준 10090번 - Counting Inversions ] 해설 및 코드

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

목적

배열에서 inversion count를 구하자.

 

접근법

1. inversion count는 문제에도 나와있듯이, 역순으로 된 원소 쌍의 개수를 말한다. 다음과 같이 정렬을 하기 전과 한 후의 원소를 이어 생기는 교차점의 개수로 표현할 수 있다.

2. 합병정렬 알고리즘을 이용해 O(NlogN)의 시간복잡도로 구할 수 있다. 오른쪽에 있는 부분 배열의 원소가 왼쪽에 있는 부분 배열의 원소보다 작은 경우에 카운팅을 해주면 된다.

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
typedef long long ll;
 
const int MAXN=1e6+1;
int n,a[MAXN],b[MAXN];
 
ll merge(int si,int ti,int sj,int tj){
    f(i,si,tj)b[i]=a[i];
    int idx=si;
    ll cnt=0,tmp=0;
    while(si<=ti&&sj<=tj){
        if(b[si]>b[sj])a[idx++]=b[sj++],++tmp;
        else a[idx++]=b[si++],cnt+=tmp;
    }
    while(si<=ti)a[idx++]=b[si++],cnt+=tmp;
    while(sj<=tj)a[idx++]=b[sj++];
    return cnt;
}
 
ll invcnt(int l,int r){
    if(l==r)return 0;
    int mid=(l+r)>>1;
    return invcnt(l,mid)+invcnt(mid+1,r)+merge(l,mid,mid+1,r);
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;f(i,1,n)cin>>a[i];
    cout<<invcnt(1, n);
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.