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

문제

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

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

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

 

기록

(greedy 7일차) 힘들었다..! 처음엔 사람 수와 거리를 곱한 값을 사람 수로 나눈 평균거리를 계산했는데, 알고보니 합을 구하는 것과는 다른 계산이었다. 그래서 다른 방법을 검색해서 알아보았다.

 

이 문제의 핵심은 사람 수의 절반이 넘어가는 지점의 마을을 찾는 것이었다. 그런데 이 아이디어를 구현하면서도 실수를 했었는데, 마을이 위치 순서대로 나오지 않는다는 점 때문이었다. 고치니까 성공:)

 

코드

from sys import stdin
from math import ceil, floor

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

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

먼저 마을의 위치와 사람 수 정보를 저장한 뒤, 위치 기준 오름차순으로 정렬한다.

 

마을을 순차적으로 돌면서 누적사람 수가 총 사람 수의 절반이 넘어가는 지점을 찾아 출력한다.