본문 바로가기

알고리즘 문제풀이/백준 문제풀이

[BOJ 2517] 달리기

728x90
반응형

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

 

2517번: 달리기

첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다.  

www.acmicpc.net

 

세그먼트 트리(Segment Tree)를 이용한 문제이다. 

 

각 선수마다 자기보다 앞에 달리고 있는 선수들 중에서 자신보다 실력이 높은 사람의 수 + 1이 자신의 최선의 등수가 된다.  

각 선수들의 실력을 정수로 나타내었고, 실력의 범위가 1~10억이다. 

여기서 각 선수들의 실력이 모두 다르다고 하였고, 자신보다 실력이 높은 사람의 '수'만 구하면 되므로 

좌표압축 기법을 통해서 실력을 상대적인 값으로 바꿔준다. 

 

그 후, segment tree에 하나씩 추가해주면서 기존의 tree에 자신보다 높은 실력이 몇명있는지를 출력해주는 방식을 이용한다. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<algorithm>
#include<stack>
#include<cmath>
#include<functional>
#include<string>
#include<vector>
#define ll long long int
#define INT_MAX 2147483647
#define MOD 1000000007
#define MAX 500000
 
using namespace std;
int arr[MAX + 1];
int temp[MAX + 1];
int tree[4 * MAX + 1];
 
void update(int idx, int s, int e, int i);
int sum(int idx, int s, int e, int l, int r);
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N; cin >> N;
    int k;
    for (int i = 1; i <= N; i++) {
        cin >> k;
        temp[i] = k;
        arr[i] = k;
    }
    sort(temp + 1, temp + N + 1, greater<int>());
    for (int i = 1; i <= N; i++) {
        arr[i] = lower_bound(temp + 1, temp + N + 1, arr[i], greater<int>())- temp;
    }
    for (int i = 1; i <= N; i++) {
        cout << sum(11, N, 1, arr[i])+1 << '\n';
        update(11, N, arr[i]);
    }
 
}
 
void update(int idx, int s, int e, int i) {
    if (i < s || e < i) return;
 
    tree[idx]++;
    if (s != e) {
        update(idx<<1, s, (s + e) / 2, i);
        update((idx<<1+ 1, (s + e) / 2 + 1, e, i);
    }
}
int sum(int idx, int s, int e, int l, int r) {
    if (s > r || e < l) return 0;
    else if (s >= l && e <= r) return tree[idx];
    else return sum(idx<<1, s, (s + e) / 2, l, r) + sum((idx<<1)+1, (s + e) / 2+1, e, l, r);
}
 
 

33~36번째 줄이 좌표압축을 하는 과정이다. 

728x90
반응형

'알고리즘 문제풀이 > 백준 문제풀이' 카테고리의 다른 글

[BOJ 8980] 택배  (0) 2020.07.09
[BOJ 12920] 평범한 배낭 2  (3) 2020.07.07
[BOJ 2517] 달리기  (0) 2020.05.01
[BOJ 2568] 전깃줄 - 2  (0) 2020.04.22
[BOJ 11066] 파일 합치기  (0) 2019.07.22
[BOJ 1725] 히스토그램  (0) 2019.03.30