백준 - 전령들(3319)

 

문제

 

 

이 문제의 dp 점화식은 어렵지 않게 구할 수 있다.

• $\text{dp}[i]$ : i번째 정점에서 1번 정점까지 메시지를 전하는데 걸리는 최소 시간
• $\text{dp}[i] = \min_j \left( \text{dp}[p_j] - v_i d_{p_j} \right) + s_i + v_i d_i$
• $p_j$ : 현재 정점의 $j$번째 parent
• $d_i$ : 1번 정점부터 i번째 정점 까지의 거리

위 점화식의 $ \text{dp}[p_j] - v_i d_{p_j} $ 는 $ - d_{p_j} $와 $ \text{dp}[p_j] $ 를 각각 기울기와 y절편 으로 하는 직선에 대해 $x=v_i$ 일때의 값으로 볼 수 있으니까 CHT를 이용할 수 있다.

 

풀이 1 (내 풀이)

DFS로 1번 노드부터 순서대로 dp를 계산하는데 문제가 되는 부분은 직선을 삭제하는 부분이다.

이때 나는 직선을 삭제하지 않고 삭제할 직선들만 건너뛰어서 valid 한 직선들만 저장하는 sparse table을 만들었다.

 

그러면 탐색하는데 $O(N)$, 직선을 건너뛰어서 valid한 다음 직선 위치를 찾는데 $O(\log N)$ (이분탐색 이용), sparse table을 이용해서 k번째 parent를 찾는데 $O(\log N)$ 이 걸려서 최종적으로는 $O(N (\log N)^2)$ 이 걸린다.

 

풀이 2

똑같이 DFS로 탐색하는데, stack에서 직선을 삭제해야할 때 직선을 삭제하지 말고 그냥 적절한 위치에 덮어씌운다.

이때 덮어씌우기 전의 직선만 임시로 저장하면 child에 대해서 탐색을 돌고 나서 다시 복구해주기만 하면 된다.

시간복잡도는 직선의 위치를 찾을때 이분탐색을 사용하기 때문에 $O(N \log N)$ 이 걸린다.

 

아마 이 풀이가 정해인듯 하다.

 

풀이 3

Li Chao Tree 를 이용해서 풀수 있다고 한다.