[백준][Python] 2141 우체국

이분탐색으로 무게중심 찾고 그 좌우에 있는 마을만 거리비교해서 최솟값으로 가져감. 둘 거리같으면 왼쪽꺼 가져감.

import sys
input = sys.stdin.readline
from bisect import bisect_left

def cal_dist(position):
    dist = 0
    for town, population in arr:
        dist += abs(position-town)*population
    return dist


N = int(input())
arr = [tuple(map(int, input().split())) for _ in range(N)]
left = -1000000000
right = 1000000000
answer = 0
while left <= right:
    mid = (left+right)//2
    if cal_dist(mid) < cal_dist(mid+1):
        right = mid - 1
        answer = mid
    else:
        left = mid + 1
arr.sort()
close_town_idx = bisect_left(arr,(answer,0))
if cal_dist(arr[close_town_idx-1][0]) <= cal_dist(arr[close_town_idx][0]):
    answer = close_town_idx-1
else:
    answer = close_town_idx
print(arr[answer][0])

이건 그냥 어디서 다른풀이 가져옴.. 인구수합이 반이되는 지점이 해당 문제의 답이라는데

증명해놓은 사람이 아무도 없어서 좀 궁금.. 이게 왜 되는지 모르겠음

import sys
input = sys.stdin.readline


N = int(input())
postOffice = [list(map(int, input().split())) for _ in range(N)]

postOffice.sort(key=lambda x: x[0])
mid = round(sum(p for _, p in postOffice)/2)

pCount = 0
for i, p in postOffice:
    pCount += p

    if pCount >= mid:
        print(i)
        break


import sys
input = sys.stdin.readline