알고스팟 문제 링크: https://algospot.com/judge/problem/read/MORDOR
algospot.com :: MORDOR
등산로 문제 정보 문제 모르도르 지방의 아름다운 경치를 한 눈에 볼 수 있는 명산 오로드루인에는 길기로 유명한 등산로가 있습니다. 이 등산로는 산등성이를 따라 오르락내리락하며 구성되어
algospot.com
등산로에는 일정 간격으로 해발고도를 나타내는 표지판이 있다.
등산로의 부분구간을 등산하는 등산로가 있다. 등산중에 만나는 표지판중 최대 해발고도와 최소해발고도의 차이가 등산로의 난이도이다.
표지판 정보와 등산로의 구간이 주어질때 해당 등산로의 난이도를 구하는 문제이다.
등산로의 표지판 정보들을 선형탐색해서는 최대 최소를 찾는다면 시간안에 문제를 풀 수 없다.
구간 최소 쿼리(range minimun query, RMQ)를 이용하여 문제를 풀어보자.
코드 원본: https://github.com/sbl133/JongmanBook/blob/main/24.%20segmentTree/MORDOR.cpp
GitHub - sbl133/JongmanBook
Contribute to sbl133/JongmanBook development by creating an account on GitHub.
github.com
댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!
reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2
'Algorithm > algospot' 카테고리의 다른 글
| algospot 삽입 정렬 시간 재기 (문제 ID: MEASURETIME)c++ (0) | 2021.10.15 |
|---|---|
| algospot 족보 탐험 (문제 ID: FAMILYTREE) c++ (0) | 2021.10.14 |
| algospot 변화하는 중간 값 (문제 ID: RUNNINGMEDIAN)c++ (0) | 2021.10.11 |
| algospot 삽입 정렬 뒤집기 (문제 ID: INSERTION) c++ (0) | 2021.10.09 |
| algospot 너드인가, 너드가 아닌가? 2 (문제 ID: NERD2) c++ (0) | 2021.10.07 |