문제 링크
해설
일단 아무 곳이나 우체국을 놓아 봅니다.
이 때 우체국에서 모든 사람까지의 거리를 d라고 하겠습니다.
우체국을 왼쪽과 오른쪽 중 사람이 많은 곳으로 옮길수록 d는 줄어들게 됩니다.
예를 들어 우체국을 기준으로 왼쪽에 사람 5명 오른쪽에 사람 10명이 있다고 할 때,
우체국을 오른쪽으로 1만큼 움직이면 왼쪽 5명으로부터는 멀어지고 오른쪽 10명으로부터는 가까워지므로 d = d + 5 - 10 -> d = d - 5가 됩니다.
이런식으로 우체국을 사람이 많은 쪽으로 움직이다 보면,
어느 순간 왼쪽으로 가도 d가 줄지 않고 오른쪽으로 가도 d가 줄지 않는 지점에 도착하게 됩니다.
어느쪽으로 움직여도 d가 커질 수 밖에 없으니 그곳이 바로 d의 최솟값입니다. 😉
