BOJ 17261 - 석유가 넘쳐흘러
Observation
이진 트리의 특성상 모든 조상을 $O(\log N)$에 순회 할 수 있다.
부모에게서 석유가 흘러올 때, 항상 채우려는 노드 쪽으로 석유를 흘려주는 것이 최적이다.
$wlog.$ 내가 왼쪽 자식인데, 부모에게서 흘러오는 석유를 오른쪽 자식에게 먼저 채워주고 오른쪽 자식의 석유들까지 내쪽으로 끌고와서 더 빠르게 될 수 있을까?
1초마다 부모에게서 오는 석유 $p$ 와 오른쪽 자식을 채우기까지 남은 유량 $r$과 오른쪽 자식이 가진 leaf node를 $l_r$ 이라고 하자.
$r$을 모두 채우는데는 $\dfrac {r}{l_r+p}$ 초가 걸린다. 모두 채우고는 왼쪽 노드에 초마다 $l_r+p$ 의 석유가 흘러들어온다.
$r$을 모두 채우기 전까진 왼쪽 자식으로 $p$를 그냥 흘려주는게 더 이득이므로 $r$을 채운 후에 특정 시점에 더 오른쪽으로 흘려준게 이득이 되는 시점이 있나 보자.
$(l_r+p) \cdot (t - \dfrac r{l_r+p})$ 이 $t$ 초가 지났을 때 왼쪽 자식으로 흘러들어가는 양이고,
왼쪽 자식으로만 흐른다고 가정하면
$tp + l_r \cdot (t-\dfrac r{l_r})=t(p+l_r)-r$
결국 다음과 같이 되어서
$(l_r+p) \cdot (t - \dfrac r{l_r+p})=t(p+l_r)-r$
왼쪽 자식으로 흘러들어가는 양은 같으므로 항상 채우려는 쪽으로 부모의 석유를 모두 대주는게 최적이다. $\square$
Solution
Parametric Search로 각 노드마다 흐른 시간 $t$를 잡고 자기 자식 노드에서 $t$ 만큼 지나면 얻어지는 석유와 모든 조상을 순회하며 자신쪽 말고 다른쪽이 $t$ 에 스스로 모두 채워질 수 있는지를 보고 채워진다면 남은 양만큼 자신쪽에 더해준다.
위에서 증명했듯이 그리디하게 다른쪽이 스스로 채워지고 모두 자기에게만 흘려야 최적이기 때문이다.
즉, 시간복잡도 $O(Nlog ^2N)$ 에 해결 가능하다.
Comments