백준 2141번 : 우체국

https://www.acmicpc.net/problem/2141

2141번: 우체국

 

접근하기 굉장히 까다로웠던 문제. 풀이를 보고나서 이해했다.

 

일직선 상의 1차원 좌표에 N개의 마을이 있고 각 마을의 위치와 주민의 수가 입력으로 주어진다. 여기에 우체국을 세우려고 하는데, 각 마을에 살고있는 주민들이 우체국을 가기위해 이동해야 하는 거리의 총합이 최소인 위치에 세우려고 한다. 이때 우체국의 위치를 구하는 문제다.

 

문제의 예시에서처럼 3개의 마을 A마을(위치: 1, 주민: 3), B마을(위치: 2, 주민: 5), C마을(위치:3, 주민: 3)이 있다고 가정하면 위치 2에 우체국을 세우는 것이 각 마을사람들이 이동해야하는 거리(A마을(1*3) + B마을(0*5) + C마을(1*3))가 6으로 최소이다. 완전탐색으로 모든 위치에서 거리를 계산하기엔 우체국이 존재할 수 있는 위치의 범위가 너무 넓었다. 그런데 풀이를 보니 굳이 거리를 계산해 줄 필요가 없었다.

 

마을의 위치 기준으로 오름차순 정렬했을때 가장 왼쪽에 있는 마을(A라고 하자)에 주목하자. 그럼 우체국을 이 마을(A)에 설치했을때 각 마을사람들이 이동해야하는 거리의 총합을 X라고 해보자. 만약 A에서 오른쪽으로 1만큼 떨어진 곳(A+1)에 우체국을 설치한다면, A의 오른편에 위치한 그 주민들은 우체국이 가까워졌기 때문에 그 수 만큼의 이동해야하는 거리가 줄어들고 현재 A+1 위치에 있는 우체국의 왼편에 위치한 마을의 주민들은 더 멀어졌기 때문에 그 수 만큼 거리가 증가한다. 즉, 그때의 총 거리 = X - (우체국 기준 오른편의 주민들 수 - 왼편의 주민들 수)가 된다.  다시 말하면, 우체국을 오른쪽으로 이동할 수록 왼편보다 오른편 주민들의 수가 더 많으면 전체적인 거리는 계속 줄어들 것이다. 결론적으로 우체국을 오른쪽으로 점점 이동시키다가 총 거리가 이전보다 같거나 증가하게 되는 시점의 위치를 출력하면 된다.

import sys
input = sys.stdin.readline

n = int(input())
s = sorted([tuple(map(int, input().split())) for _ in range(n)])
p = [s[0][1]]
for i in range(1, n):
    p.append(p[i-1] + s[i][1])

for i in range(n):
    if p[-1] <= 2*p[i]:
        print(s[i][0])
        break