[BOJ] 2517 : 달리기

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

---

세그먼트트리

[ 문제해석 ]

 

 현재 달리고 있는 선수들의 순서대로 선수들의 능력치가 입력으로 들어옵니다. 이때, 자기 능력치보다 적은 선수가 앞에서 달리고 있으면 '앞지를 수 있는 가능성' 이 존재합니다. 선수들의 능력치가 입력으로 들어왔을 때 각 선수가 얻을 수 있는 최선의 등수를 찾는 문제입니다.

 

[ 알고리즘풀이 ]

 

1) '선수가 얻을 수 있는 최선의 등수' = '지금 등수' - '앞지를 수 있는 선수의 수' 를 이용하면 됩니다. 즉 내가 3등인데 앞에 2명을 앞지를 수 있으면 최선의 등수는 1등이 됩니다.

 이때, '앞지를 수 있는 선수' 는 나보다 앞에 있으면서 능력치가 나보다 작은 선수가 됩니다.

 --> "나보다 앞의 범위에서 능력치가 나보다 작은 선수를 count 하자!" 로 문제를 단순화 할 수 있습니다. 

 --> 세그먼트 트리를 이용해 앞의 범위에서 능력치가 나보다 작은 선수를 count 하자!

 

2) N은 500,000 지만 입력되는 범위는 1 ~ 10^9이므로 좌표압축을 통해서 능력치 대신에 능력치를 낮은 순으로 등수를 매긴 값으로 갱신해줍니다.

 예제를 보면 [ 2, 8, 10, 7, 1, 9, 4, 15 ] 능력치를 입력받습니다.

 이를 능력치 낮은 순으로 [ 2, 5, 7, 4, 1, 6, 3, 8 ] 로 등수를 매겨 새롭게 값을 갱신해줍니다. 

 

3) 등수를 이용해 세그먼트 트리를 만듭니다.

 0으로 초기화된 세그먼트 트리에서 앞의 선수부터 등수에 해당하는 인덱스를 '1'로 세그먼트 트리를 갱신합니다.  따라서, 자신보다 앞에 있는 범위를 전체 sum 한다면 자신보다 앞에 있는 능력치가 작은 선수들을 한 번에 count 할 수 있게 됩니다.

 

예제를 통해 생각해보겠습니다. 

 

능력치  [ 2, 8, 10, 7, 1, 9, 4, 15]

등수 [ 2, 5, 7, 4, 1, 6, 3, 8 ]

초기세그먼트 [ 0 0 0 0 0 0 0 0 ]

--> '능력치 낮은 순 2등' 세그먼트트리 [ 0 1 0 0 0 0 0 0 ]

--> (1~1 범위를 sum) = 0 이므로 0명을 앞지를 수 있다. --> (현재1등) - (0명) = 최대 1등

--> '능력치 낮은 순 5등' 세그먼트트리 [ 0 1 0 0 1 0 0 0 ]

--> (1~4 범위를 sum) = 1 이므로 1명을 앞지를 수 있다. --> (현재2등) - (1명) = 최대 1등

--> '능력치 낮은 순 7등' 세그먼트트리 [ 0 1 0 0 1 0 1 0 ]

--> (1~6 범위를 sum) = 2 이므로 2명을 앞지를 수 있다. --> (현재3등) - (2명) = 최대 1등

 

 위와 같은 과정을 반복하면 된다.

 

[ 코드 C++ ]

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
 
using namespace std;
 
const int N_MAX = 500000;
int ab[N_MAX];
vector<int> sortedAb;
ll tree[4 * N_MAX];
 
ll sum(int index, int start, int end, int left, int right) {
    if (end < left || right < start)
        return 0;
    if (left <= start && end <= right)
        return tree[index];
    int mid = (start + end) / 2;
    return sum(2 * index + 1, start, mid, left, right) + sum(2 * index + 2, mid + 1, end, left, right);
}
 
ll update(int index, int start, int end, int changed, int diff) {
    if (changed < start || end < changed) return tree[index];
    if (start == end) return tree[index] = diff;
    int mid = (start + end) / 2;
    return tree[index] = update(index * 2 + 1, start, mid, changed, diff) + update(index * 2 + 2, mid + 1, end, changed, diff);
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> ab[i];
        sortedAb.push_back(ab[i]);
    }
    sort(sortedAb.begin(), sortedAb.end());
 
    for (int i = 0; i < N; i++) {
        int ind = (lower_bound(sortedAb.begin(), sortedAb.end(), ab[i]) - sortedAb.begin());
        update(0, 0, N - 1, ind, 1);
        cout << (i + 1) - sum(0, 0, N - 1, 0, ind - 1) << '\n';
    }
    return 0;
}

https://github.com/travelbeeee/BOJ/blob/master/BOJ2517.cpp

travelbeeee/BOJ

---