[BOJ] 9006. 다리

문제 링크

강의 왼쪽에 $n$개, 오른쪽에 $m$개의 집이 있습니다. 왼쪽에 있는 집의 좌표는 $(-1, a_{i})$, 오른쪽에 있는 집의 좌표는 $(1, b_{j})$이고 왼쪽 집에서 오른쪽 집으로 가는 모든 거리의 합을 최소화하는 다리의 위치를 출력해야 합니다. 즉, $\displaystyle\sum_{\forall i, j} {(|a_{i} - h| + 2 + |b_{j} - h|)}$의 값이 최소가 되는 $h$를 찾아 출력하면 됩니다.

먼저 $\displaystyle\sum_{\forall i, j} {(|a_{i} - h| + 2 + |b_{j} - h|)}$는 $2mn + m \cdot \displaystyle\sum_{i=1}^{n} |a_{i} - h| + n \cdot \displaystyle\sum_{j=1}^{m} {|b_{j} - h|}$와 값이 같습니다.

$h$값에 따라 위 식은 $Ah+B$꼴로 표현할 수 있습니다. 또한 $h$ 값이 커지면 커질수록 $A$ 또한 단조증가합니다. 즉, $h$를 절댓값이 충분히 큰 음수부터 시작해서 값을 늘려나가면 위 식의 값은 작아지다가 어느 순간 커지게 됩니다. 그리고 증가/감소 상태가 바뀌는 시점의 $h$ 값이 위 식의 값이 최소가 되는 지점입니다.

우리는 값이 최소가 되는 $h$ 중에서 가장 작은 값을 출력해야 하므로 $h$를 절댓값이 충분히 큰 음수부터 시작해서 점차 늘려가면서 $A$값을 확인하다가 $A \geq 0$이 되는 순간의 $h$ 값을 출력하면 됩니다. 시간복잡도는 $O((n+m)\log{(n+m)})$입니다.