[백준 2285번] 우체국 (python)

문제

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

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

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

 

기록

(greedy 8일차) 똑같은 문제였다!

>> 2021.07.19 - [알고리즘] - [백준 2141번] 우체국 (python)

[백준 2141번] 우체국 (python)

 

코드

from sys import stdin

N = int(stdin.readline())
villages = []
people=0
for _ in range(N):
    pos, peo = map(int, stdin.readline().split())
    villages.append((pos, peo))
    people += peo
villages.sort(key=lambda x : x[0])

count = 0
for pos, peo in villages:
    count+=peo
    if count>(people/2):
        print(pos)
        break

사람이 절반이 넘어가는 시점의 마을 찾아 출력했다.