[알고리즘] 편의점2 - 백준 14400 파이썬

문제

영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고객들이 어느 위치에 존재하는지 파악을 하였고, 모든 고객들의 거리의 합을 최소로 하려한다. 두 위치의 거리는 |x1-x2|+|y1-y2|로 정의한다.

n명의 주요 고객들의 위치 (xi,yi)이 주어질 때, 모든 고객들의 거리 합을 최소로 하는 위치에 편의점을 세울 때, 그 최소 거리 합을 출력하시오.

입력

첫째 줄에는 주요 고객들의 수n이 주어진다.(1≤n≤100,000)

다음 n줄에는 고객들의 위치 (x,y)가 주어진다.(-1,000,000≤x,y≤1,000,000)

출력

모든 고객들의 거리 합을 최소로 하는 위치에 편의점을 세울 때, 그 최소 거리 합을 출력하시오.

import sys


def sol(lst):

    lst = sorted(lst, key=lambda x: x[0])

    x = lst[int(n/2)][0]

    lst = sorted(lst, key=lambda x: x[1])

    y = lst[int(n/2)][1]

    res = 0

    for i in range(n):
        res+=abs(x-lst[i][0])+abs(y-lst[i][1])

    print(res)

    pass


if __name__ == '__main__':

    with open('testcase_14400.txt') as f:
        sys.stdin = f
        input = sys.stdin.readline

        n = int(input())

        lst = []

        for _ in range(n):
            lst.append(list(map(int,input().split())))


        result = sol(lst)

각 x좌표와 y좌표의 값에 대하여 평균값을 점으로 구하려고 하니 답이 나오지 않았고,

주어진 좌표들 중, 중간값인 x와 중간값인 y를 구하고

해당 지점으로부터 각 점까지의 거리를 구하여 더한다.