[백준] 2141번 - 우체국 Python

문제

---

수직선과 같은 일직선상에 N개의 마을이 위치해 있다. i번째 마을은 X[i]에 위치해 있으며, A[i]명의 사람이 살고 있다.

이 마을들을 위해서 우체국을 하나 세우려고 하는데, 그 위치를 어느 곳으로 할지를 현재 고민 중이다. 고민 끝에 나라에서는 각 사람들까지의 거리의 합이 최소가 되는 위치에 우체국을 세우기로 결정하였다. 우체국을 세울 위치를 구하는 프로그램을 작성하시오.

각 마을까지의 거리의 합이 아니라, 각 사람까지의 거리의 합임에 유의한다

입력

---

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.

출력

---

첫째 줄에 우체국의 위치를 출력한다. 가능한 경우가 여러 가지인 경우에는 더 작은 위치를 출력하도록 한다.

예제 입력 1

---

3
1 3
2 5
3 3

예제 출력 1

---

2

풀이

---

Python

import sys
input = sys.stdin.readline

n = int(input().rstrip())
p = []
answer = 0
totalp = 0

for _ in range(n):
    v_n, v_p = map(int,input().rstrip().split())
    totalp += v_p
    p.append([v_n,v_p])

p.sort(key=lambda x : x[0])

# 인구의 합이 절반에 속하는 부분에 우체국을 설치하는 게 좋다.
cnt = 0
for i in range(n):
    cnt+=p[i][1]
    if cnt >= totalp/2:
        answer = p[i][0]
        break
print(answer)

정리

---

• 누적 합이 인구의 절반이 넘는 부분에 설치하면 된다.