이번 문제는 그리디 알고리즘을 통해 해결하였다. 우선 마을 리스트를 위치의 오름차순으로 정렬하고, 모든 마을의 인구의 총 합을 구한다. 그리고 이의 절반 값 mid를 구한다. 마을 리스트를 순회하며 인구의 누적합을 구하며, 누적합이 mid보다 크거나 같다면, 이 마을에 우체국을 세워야 한다. 그러므로 결과 변수에 현재 위치를 저장하고, 종료한다.

Code

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