이번 문제는 그리디 알고리즘을 통해 해결하였다. 이전에 푼 문제와 같은 문제 같았지만, 다시 풀어보는 마음으로 다시 풀었다. 입력받은 데이터를 위치의 오름차순으로 정렬하고, 전체 사람들의 합을 구한 후, 이의 중간값을 구한다. 그리고 데이터를 순회하며 사람들의 합을 누적해가며 누적된 사람의 수가 중간값을 넘어갈 경우에 해당 위치에 우체국을 세우면 적절한 위치가 된다.

Code

n = int(input())
town = sorted([list(map(int, input().split())) for _ in range(n)], key= lambda x: x[0])
total = 0
for i in range(n):
    total += town[i][1]
mid = total//2
if total%2 == 1:
    mid += 1
cur = 0
answer = 0
for i in range(n):
    cur += town[i][1]
    if cur >= mid:
        answer = town[i][0]
        break
print(answer)