[python] 백준 2141 우체국

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

2141번: 우체국

 

문제 해결

$ L_{1} $ 공간에서 $ \sum_{i=1}^{n} |x_{i}-a| \times b $ 의 최솟값은 표본의 중앙값이 위치한 값이라는 것을 이용하는 문제이다.

https://math.stackexchange.com/questions/4410205/minimum-value-of-sum-of-absolute-diferences

minimum value of sum of absolute diferences

 

 

CODE

import sys
INF = sys.maxsize
n = int(input())
location = []
p = 0
for i in range(1,n+1):
    a, b = map(int, input().split())
    location.append([a,b])
    p += b
location.sort(key= lambda x : x[0])

cnt = 0
for i in range(n):
    cnt += location[i][1]
    if cnt >= p/2:
        print(location[i][0])
        break