BOJ 24026 - 기차 여행

BOJ 24026 - 기차 여행

Sparse Table로 구성해보자.

$L[k][i], R[k][i]$ 를 $i$ 에서 $2^k$ 번 이동할 때 최대로 이동할 수 있는 가장 작은 도시와 가장 큰 도시라고 하자.

이를 채우는건 Segment Tree로 할 수 있다.

자신이 $2^{k-1}$ 번에 $l, r$ 까지 도달할 수 있었다면 $2^{k-1}$ 번 이동해서 도달하는 값들이 저장된 세그먼트 트리에 $l, r$ 부분에 또 쿼리를 날려 $2^k$ 번 이동해서 갈 수 있는 도시들의 값을 얻어오게 된다.

따라서 전처리에 $O(N \log ^2N)$ 이 소요된다.

이제 정답을 이분탐색을 이용해 구하면 된다.

세그먼트 트리와 Sparse Table을 쓰는것까지 생각했고, 실제로 답을 구하려 했지만 내가 짠 알고리즘이 $O(N \log ^3N)$ 이라 무지성 TLE를 끝없이 받게되었다.

어찌됐든 이 시간복잡도로 극한의 최적화를 해 통과할 수는 있었지만, $O(N \log ^2N)$ 을 하는 방법은 전처리된 세그먼트 트리를 배열을 이용한 RMQ로 $O(1)$에 쿼리할 수 있게 한 번 더 전처리를 하는 것인것같다.