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

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

문제

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

의식의 흐름 및 해설

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

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

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

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

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

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

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

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

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

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

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

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

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

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

코드

#include #include #include #define all(v) (v).begin(), (v).end() using namespace std; typedef long long ll; const int MAX = 500001; vector 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) << "

"; update(1, 1, N, a[i], 1); } }

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

from http://kth990303.tistory.com/108 by ccl(A) rewrite - 2021-08-06 22:26:22