백준 2141 우체국

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

2141번: 우체국

📌 해결 과정

우체국은 마을에 설치 하는 것이고,

우체국과 각 마을까지의 거리가 아니라 각 마을에 사는 사람들과의 거리 합을 기준으로 설치 할 위치를 정해야함에 유의해야 한다.

따라서, 설치 할 위치에 영향을 주는 것이 거리가 아닌 사람 수 임을 알 수 있다.

 

핵심은, 현재 마을의 양 옆에 마을 사람들의 수가 가장 균등하게 나눠지는지 판단하는 것이다.

그 기준은 현재 까지 더한 각 마을 사람들의 수의 합이 (전체 마을 사람들의 수 / 2) 보다 커지는지 비교해 보는 것이다. 

 

📌 코드

import sys

input = sys.stdin.readline

N = int(input())
people_total = 0
datas = []

for _ in range(N):
    viliage, people = map(int, input().split())
    datas.append([viliage, people])
    people_total += people

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

people_tmp = 0
mid = people_total / 2

for i in range(N):
    people_tmp += datas[i][1]
    if people_tmp >= mid:
        print(datas[i][0])
        break