[백준] 2517: 달리기

0. 문제 주소

 

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

2517번: 달리기

 

 

1. 풀이

 

inversion 개수를 구하는 문제.

 

강사님이 merge sort를 구현하면서 inversion을 구할 수 있다고 하셨고, 이해도 갔지만 구현이 어려울 것 같았다.

 

그래서 ICPC를 준비하며 봤던 내용으로 인덱스 트리 / 펜윅 트리를 이용해서 구했다.

 

 

 

 

2 4 1 3 5라는 배열의 inversion을 구해보자. inversion은 위와 같이 같은 원소들을 정렬해놓고 화살표로 이었을 때,

 

선들끼리의 교차점의 개수라고 생각해도 된다.

 

윗줄의 맨 첫 번째 원소부터 화살표를 따라 아랫줄로 방문을 시작한다.

 

 

 

윗 줄의 가장 첫 원소인 2를 화살표를 따라 밑줄에서 방문하고,

방문한 위치 다음 원소부터 끝까지 이미 방문한 원소가 몇개인지 세어준다.

 

처음 방문한 거라 아직 0개이다. 왜 이렇게 해야 하는지 감이 안 잡힐 테니 다음 원소를 방문해보자.

 

 

 

윗줄의 4를 밑줄에서 찾아 방문했고, 이번에도 오른쪽 너머에서 이미 방문한 원소들의 개수는 0이다.

 

 

 

 

윗줄의 1을 아랫줄에서 방문했더니, 오른쪽에서 이미 방문한 원소의 개수가 2라고 한다. 이게 무슨 말일까?

 

 

inversion의 정의는, 크기 순서가 뒤집어져 있는 순서쌍의 개수이다.

원래 배열 2 4 1 3 5에서, 크기 순서가 뒤집어져 있는 순서쌍은 (2, 1), (4, 1), (4, 3) 총 3개이다.

 

윗줄의 1을 아랫줄에서 방문하기 위해 파란색 화살표를 그리려 할 때,

1보다 더 큰 크기 순서를 가지는 2와 4에 대해선 이미 초록색 화살표가 그어져 있는 상태이다. 

 

즉 윗줄에서 이번에 방문하려는 원소 N에 대해,

앞서 N보다 큰 원소들이 몇 개나 있었는지 세어주는 작업이 위에서 서술한 내용인 것이다.

 

 

이는 원소의 변경이 자주 일어나는 구간합 문제를 풀 때 유용하게 쓸 수 있는

인덱스 트리 / 펜윅 트리를 이용해 풀 수 있다.

 

 

유의해야 할 점은, 정수들의 크기 제한이 10억 이하인 자연수 이므로 map이나 pair를 통해 좌표 압축을 거친 뒤 

트리를 구성해야 한다.

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <iostream>
#include <map>
#include <algorithm>

#define MAX 500005


using namespace std;

int N;
int arr[MAX];
int des_arr[MAX];
int ftree[MAX];
map<int, int> mp;

int Li(int x){
    return x&(-x);
}

int get_sum(int x){
    int ret = 0;
    while(x>0){
        ret += ftree[x];
        x -= Li(x);
    }
    return ret;
}

void update(int x, int diff){
    while(x<MAX){
        ftree[x] += diff;
        x += Li(x);
    }
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    scanf("%d", &N);
    for (int i=1;i<=N;i++){
        scanf("%d", &arr[i]);
        des_arr[i] = arr[i];
    }
    
    sort(des_arr+1, des_arr+N+1, greater<int>());
    
    for (int i=1;i<=N;i++){
        mp[des_arr[i]] = i;
    }
    
    for (int i=1;i<=N;i++){
        int curr_val = arr[i];
        int sorted_pos = mp[curr_val];
        printf("%d\n", i - (get_sum(N) - get_sum(sorted_pos)));
        update(sorted_pos, 1);
    }
    
    return 0;
}