BOJ 14589 - Line Friends (Large)

slah007 선배의 추천으로 풀게 된 문제이다. 푼지는 좀 됐는데, 시험기간 탓에 이제야 포스팅한다.

 

문제 요약

구간 \([L, R]\) 로 나타내어지는 선분 \(N\)개가 주어진다. 만약 두 선분이 겹칠 경우, 두 선분 사이의 거리를 1로 정의한다. \(A\)번 선분과 \(B\)번 선분의 거리를 구하는 쿼리를 \(Q\)번 처리하라.

 

풀이

일반성을 잃지 않고 두 선분이 겹치지 않으며 A가 B보다 앞에 있다고 가정하자.

당연하게도, B에 도달하기 위해서는 매 이동마다 가장 끝 좌표가 큰 선분으로 이동하는 것이 최적이다.

이렇게 같은 행동을 반복하는 문제는 DP, 그 중에서도 Sparse Table을 사용하면 해결할 수 있다.

다만, Sparse Table을 만들기 위해서 몇 가지 생각해야 할 부분이 존재한다.

먼저, 좌표 범위가 넓기 때문에 각 좌표별로 DP 배열을 만들수는 없다. 따라서, 각 선분에 대해서 \(2^i\)번의 시행을 통해 도달할 수 있는 가장 끝 좌표가 큰 선분의 번호를 DP 배열에 저장해주어야 한다.

이를 위해서는 초항, 즉 각 선분에 대해 1번의 이동으로 갈 수 있는 끝 좌표가 가장 큰 선분의 번호를 구해주어야 한다.

이는 각 선분마다 나의 끝 좌표보다 시작 좌표가 작은 선분 중 끝 좌표가 가장 큰 선분을 고르는 것과 동치이므로, 선분을 끝 좌표 순으로 정렬한 후 셋 + 스위핑 또는 세그먼트 트리를 사용하면 구할 수 있다.

Sparse Table을 만든 후에는 LCA를 구할 때와 비슷한 Binary Shifting을 사용해 이동 횟수를 구해주면 된다.

이 때 B번 선분으로 도달하지 못하는 경우를 처리해주어야 하는데, 이는 이동 횟수가 \(N\)보다 큼과 동치임을 이용해 처리해줄 수 있다.

 

비슷한 방법으로 24026도 해결할 수 있다. 다만, 이 문제는 RMQ가 필요해서 세그나 추가적인 희소 테이블을 만들어주어야 한다.