(M - 1696. Jump Game VI) PQ, Monotone Queue 테크닉

그냥 DP로 접근해서, 각 노드마다 앞 (Bottom-up의 경우; Top-down이면 뒤) K 범위 탐색 : O(NK)

K 범위 탐색 자체를 줄이지 않는 이상, 기타 잡다한 최적화는 효과 없음

 

 

그럼 어떻게?

→ 문제를 바꿔서 생각해보자 (환원)

본질은, K 범위 내의 DP 값 중에서 max값만 뽑아내는 것.

딱 Heap 쓰면 될 것 같지 않음?

 

다만, K범위에서 벗어난 값이 있으면 pop 해줘야 하니, idx랑 같이 저장해서 매번 범위 내인지 체크

PQ 자체가 넣고 빼는데 O(logN)이라, 그래도 O(NlogK) 나옴.

(Sol 3 - Priority Queue)

---

시간 더 줄이는 방법 존재. push pop이 O(1)인 deque를 써서 PQ처럼 쓰면 됨.

Monotone Queue Technique

https://goldenriver42.tistory.com/135?category=923015

 

이러면 O(N)만에 가능