Baekjoon(백준) 2141번 - 우체국

백준 사이트의 2141번 문제이며 문제 제목은 우체국.
백준 2141
가볍게 풀 수 있는 문제이다.

문제 해석

수직선 상에 N개 마을이 있고 각 마을마다 좌표와 사는 사람 수가 주어진다.

(마을과 우체국 사이 거리) X (마을 사람 수) 의 합

이 값 (dist 라고 하겠다) 이 최소가 되는 우체국의 위치를 구하는 것이다.

풀이 전략 1

무식하게 가보는 방법이다. brute force method 로 우체국의 위치를 가장 왼쪽에 있는 마을부터 가장 오른쪽에 있는 마을가지 변화시키면서 각각 dist를 계산하여 가장 작은 dist 를 가지는 우체국의 위치를 특정하면 된다. 한 마디로 그냥 모든 경우의 수를 다 때려박으면 된다. 그렇게 되면 시간 복잡도는 O(N^2) 이고, 약 100억번의 계산을 해야 한다. 그런데 시간 제한이 2초라서 약 2억번의 계산을 넘게 되면 TLE (Time Limit Exceeded) 처리가 된다. 부분점수 없는 문제라서 그러면 그냥 끝이다. 안되는 방법이다.

풀이 전략 2 - 좀 더 발전된…

그러면 좀 더 머리를 써보자. greedy algorithm 을 고안해볼 것이다.
아무런 지점 x에 우체국이 있다고 하자. 만약 우체국이 x+1 로 이동하면 x 좌표의 왼쪽에 있던 사람 수만큼 dist가 증가하고, 오른쪽에 있던 사람 수만큼 dist가 감소한다. 반대로 x - 1로 이동하면 왼쪽에 있던 사람 수만큼 dist가 감소하고, 오른쪽에 있던 사람 수만큼 dist가 증가한다. 즉, 오른쪽에 더 많은 사람 수가 있다면 오른쪽으로 우체국을 이동하고, 왼쪽에 더 많은 사람이 있다면 왼쪽으로 우체국을 이동하는 것이 이득인 것을 알 수 있다.
앞에서 설명한 대로 우체국의 위치를 이동하게 되면 결국 dist가 최소가 되는 optimal 한 우체국의 위치는

우체국 위치를 기준으로 왼쪽에 있는 인구수와 오른쪽에 있는 인구수가 같은 (가장 차이가 적은) 곳

임을 알 수 있다. 우체국의 위치는 수학적으로 생각해보면 항상 각 마을의 좌표들 중 하나가 되어야 하고, 그렇다면 양쪽의 인구가 완전히 같은 우체국의 위치도 있겠지만 아닌 경우가 더 많을 것이다. 그런 경우에는 양쪽의 인구수 차이가 가장 작은 위치로 잡으면 된다. 시간 복잡도는 O(N) 이라서 문제에서 주어진 시간 제한을 만족한다.

자세한 코드는 github에 있다.

baekjoon 2141 solution code