BOJ 15745 Snow Boots
알고리즘 문제풀이/BOJ
2020. 1. 23. 03:50
난이도 : Solved ac 기준 Platinum 5 출처 : USACO 2018 Feburary Contest Gold - Problem 1 1. 문제 설명 높이 배열 $A$ 와 쿼리 10만 개가 주어진다. 각 쿼리는 $s_i$ 와 $d_i$ 로 구성되어 있는데, $s_i$ 는 지나갈 수 있는 최대 높이를 의미하고, $d_i$ 는 건너뛸 수 있는 최대 점프 크기를 의미한다. 즉, $d_i$ 이하의 점프로 1번부터 $N$번까지 뛰어가는데, $s_i$ 보다 높은 점을 밟지 않고 갈 수 있는지 여부를 빠르게 판정해야 한다. 예를 들어, 높이 배열이 $\texttt{0 3 8 5 6 9 0 0}$ 이고, $s_i = 4, d_i = 3$ 이라면 지나갈 수 없다. 1번에서 시작해서 2번까지 가더라도 3, 4, ..
