[BOJ 10513] 외계 침략자

문제: https://www.acmicpc.net/problem/10513

 

풀이:

거리가 가장 먼 것 부터 터트리는 것을 생각합시다. 해당 우주선을 $t$ 시간에 터트리면 해당 $t$ 시간이 포함되는 모든 우주선은 같이 터지게 됩니다. 즉, $t$ 시간이 배제된 ($t$ 시간 이전에 없어지거나 $t$ 시간 이후에 나타나는) 우주선만 고려하면 되고, 이 두 우주선은 따로 고려할 수 있습니다.

 

$D_{a, b}$를 $[a, b)$ 시간에 완전히 포함되는 우주선만을 처치하는데 드는 최소 비용이라고 합시다. ($a-1$ 시간과 $b$ 시간에 폭탄을 터트린 경우입니다. 가장 먼 거리의 우주선이 $[l, r)$ 시간에 있고, 거리가 $d$ 라고 하면 $D_{a, b} = \max_{l \le i < r} (d + D_{a, i} + D_{i+1, b})$가 됩니다.

 

코드: https://www.acmicpc.net/source/share/66e80b2f59694a06804329db4e0e62ef