- Today
- 27
- Total
- 237,967
Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Archives
- 2022/06 (8)
- 2022/05 (5)
- 2022/04 (11)
- 2022/03 (11)
- 2022/02 (1)
- 2022/01 (2)
- 2021/11 (2)
- 2021/10 (2)
- 2021/09 (4)
- 2021/02 (1)
- 2020/07 (1)
- 2020/06 (6)
- 2020/05 (5)
- 2020/04 (5)
- 2020/03 (5)
- 2020/02 (6)
- 2020/01 (6)
- 2019/12 (7)
- 2019/11 (8)
- 2019/09 (7)
- 2019/06 (2)
- 2019/05 (6)
- 2019/04 (4)
- 2019/03 (8)
- 2019/02 (5)
- 2019/01 (2)
- 2018/11 (7)
- 2018/10 (10)
- 2018/09 (2)
- 2018/07 (2)
Joonas' Note
BOJ 9034 - 순위 본문
링크: https://www.acmicpc.net/problem/9034
오랜만의 포스팅. 아마 한동안 문제를 풀 시간은 없을 듯.. ㅠ
문제
매번 \(i\)번 선수에게 더해지는 점수가 주어지고, \(x\)번째 선수가 몇 등인지 실시간으로 출력하는 문제이다.
먼저 어떤 선수의 등수는 "그 선수보다 점수가 더 높은 사람의 수 + 1"이다.
매번 탐색을 하거나, 정렬을 한다면 \(100,000\)명의 선수에 대한 \(200,000\)번의 질의에 대답하기엔 시간상으로 버겁다.
내 등수는 구간 [내 점수 + 1, ∞)에 있는 사람의 수 + 1과 같다. 점수의 합은 최대 \(10^{9}\)이므로, 모든 점수를 압축할 필요가 있다.
이건 좌표압축 문제(BOJ 18870 - 좌표 압축)를 먼저 풀어보기를 권장한다.
점수가 더해질때마다, 이전의 내 점수 위치를 -1하고 새로 더해진 점수 위치를 +1하여 나중에 카운팅될 수 있도록 업데이트하면 된다.
코드
반응형
'알고리즘 > 문제 풀이' 카테고리의 다른 글
BOJ 3640 - 제독 (0) | 2020.05.24 |
---|---|
BOJ 15480 - LCA와 쿼리 (0) | 2020.05.15 |
BOJ 9034 - 순위 (0) | 2020.05.01 |
BOJ 1539 - 이진 검색 트리 (4) | 2020.04.17 |
BOJ 18109 - 도깨비불 (0) | 2020.04.02 |
SWEA 2112 - [모의 SW 역량테스트] 보호 필름 (0) | 2020.02.26 |
0 Comments