[PS] 백준 #2517. 달리기

문제 정보

• 난이도: 플래티넘 IV
• 문제 주소: https://www.acmicpc.net/problem/2517
• 이 문제를 푼 이유: 알고리즘 스터디 - 세그먼트 트리

 

문제

KOI 장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. 각 선수의 입장에서 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 남은 거리 동안 앞지르는 것은 불가능하다. 반대로, 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있으면 남은 거리 동안 앞지르는 것이 가능하다. 이러한 가정 하에서 각 선수는 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다.

각 선수의 평소 실력은 정수로 주어지는데 더 큰 값이 더 좋은 실력을 의미한다. 현재 달리고 있는 선수를 앞에서 부터 표시했을 때 평소 실력이 각각 2, 8, 10, 7, 1, 9, 4, 15라고 하면 각 선수가 얻을 수 있는 최선의 등수는 (같은 순서로) 각각 1, 1, 1, 3, 5, 2, 5, 1이 된다. 예를 들어, 4번째로 달리고 있는 평소 실력이 7인 선수는 그 앞에서 달리고 있는 선수들 중 평소 실력이 2인 선수만 앞지르는 것이 가능하고 평소실력이 8과 10인 선수들은 앞지르는 것이 불가능하므로, 최선의 등수는 3등이 된다.

선수들의 평소 실력을 현재 달리고 있는 순서대로 입력 받아서 각 선수의 최선의 등수를 계산하는 프로그램을 작성하시오.

 

나의 풀이

이 문제는 앞의 Counting Inversions 문제와 비슷해보였는데.. 아까는 10만이 최대였지만 이 문제는 10억이 최대다. 따라서 10억칸의 세그먼트 트리를 만들 수가 없다. 오랫동안 고민하다 값을 강제로 1~50만으로 만드는 방법이 떠올랐다. 오름차순으로 값을 정렬한 뒤 해당 Index를 그 값 대신 부여하는 것이다. 이 과정은 map으로 기존 값 : 새로운 값을 저장하여 구현했다. 나머지 과정은 Counting Inversions 문제와 코드가 똑같다.

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> tree;

void update(int idx, int value) {
    for (tree[idx += n] = value; idx > 1; idx >>= 1)
        tree[idx >> 1] = tree[idx] + tree[idx ^ 1];
}

long long query(int l, int r) {
    // sum interval [l, r)
    long long ret = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l % 2) ret += tree[l++];
        if (r % 2) ret += tree[--r];
    }
    return ret;
}

int main() {
    cin.tie(NULL);	cout.tie(NULL);	std::ios::sync_with_stdio(false);

    cin >> n;
    tree.resize(4 * n + 1, 0);
    vector<int> vec(n);
    for (int i = 0; i < n; i++) cin >> vec[i];

    // 좌표 정렬 후 map 으로 부여
    vector<int> tempvec = vec;
    sort(tempvec.begin(), tempvec.end());
    map<int, int> vecmap; 
    for (int i = 0; i < n; i++) {
        vecmap[tempvec[i]] = i + 1; 
    }
    vector<int> newvec(n);
    for (int i = 0; i < n; i++) {
        newvec[i] = vecmap[vec[i]];
    }

    // Make Segment Tree : default는 모두 0으로 초기화

    // Find Answer
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans = query(newvec[i] + 1, n + 1);
        update(newvec[i], 1);
        cout << ans + 1 << "\n";
    }
}