2141번 우체국

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

---

아이디어

누적 인구가 중간 위치 이상에 도달하는 마을을 찾으면 되는 문제이다.

해야할 것은 마을을 오름차순으로 정렬한 후, 인구의 중간값을 찾아야한다.
여기서 내가 틀렸던 건데 만약 인구수가 홀수일 때는 2로 나눈 몫에다가 +1을 해주어야한다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n) ]
arr.sort(key=lambda x: x[0]) # 마을 순서로 정렬

people = sum(arr[i][1] for i in range(n)) # 사람들 총 몇 명인지
if people % 2 != 0:
    people = people // 2 + 1 # 중앙값
else:
    people //= 2

temp = 0
result = 0 # 정답이 될 마을
for i in range(n):
    temp += arr[i][1]
    if temp >= people:
        result = arr[i][0] # 마을
        break
print(result)