[BOJ] 백준 2517. 달리기 (Platinum IV)

문제

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

2517번: 달리기

---

의식의 흐름 및 해설

 

처음 볼 때 생각난 것은 당연히 세그먼트트리이다.

세그먼트트리의 정석이라 불릴만한 문제이기 때문이다.

 

물론 세그먼트트리에 익숙하지 않다면 그리디나 누적합을 떠올릴 수도 있겠지만,

이 문제는 inversing counting 알고리즘과 워낙 유사하여 세그먼트트리를 떠올릴 수밖에 없는 문제이다.

 

그런데 생각했던 것보다는 조금 더 난이도가 있었다.

바로 '이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다' 라는 문장 때문이다.

 

따라서 배열에 값을 집어넣을 수가 없으나,

N은 최대 50만이고, 모든 값이 다 다르기 때문에 좌표압축을 해준다면 충분히 가능하다.

좌표압축을 하는 방법엔 여러 가지가 있다.

index를 추가로 저장해 sorting 후 압축하는 방법도 있으나, 나는 lower_bound를 이용하는 방법을 사용했다. (그게 그거긴 하지만...)

 

각 실력을 int a[MAX], vector<int> v에 같이 입력받고, v만 sorting해준 후,

실력이 몇 번째 등수인지 파악해주기 위해 lower_bound를 사용해주면 된다.

 

그 외 나머지는 Inversing_counting 알고리즘과 같다.

구간합 세그먼트트리를 만든 후, 각 실력에 따른 쿼리 호출 후 그 실력에 해당하는 리프노드를 +1 update해주면 된다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const int MAX = 500001;
vector<int> v;
int N, a[MAX], tree[1 << 20];
int query(int node, int s, int e, int left, int right) {
	if (e < left || right < s)
		return 0;
	if (left <= s && e <= right)
		return tree[node];
	int mid = (s + e) / 2;
	return query(node * 2, s, mid, left, right)
		+ query(node * 2 + 1, mid + 1, e, left, right);
}
void update(int node, int s, int e, int idx, int val) {
	if (e < idx || idx < s)
		return;
	tree[node] += val;
	if (s != e) {
		int mid = (s + e) / 2;
		update(node * 2, s, mid, idx, val);
		update(node * 2 + 1, mid + 1, e, idx, val);
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;
	v.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		cin >> v[i];
		a[i] = v[i];
	}
	sort(all(v));
	for (int i = 1; i <= N; i++) {
		a[i] = lower_bound(all(v), a[i]) - v.begin() + 1;
		cout << i - query(1, 1, N, 1, a[i] - 1) << "\n";
		update(1, 1, N, a[i], 1);
	}
}

생각보다 많은 사람들이 해결해 신기했던 문제.