[백준 14400번] 파이썬 - 편의점 2

백준 14400 - 편의점2

시간 제한 2초, 메모리 제한 512MB

# 조건

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

입력

• 첫째 줄에는 주요 고객들의 수n이 주어진다.(1≤n≤100,000)
• 다음 n줄에는 고객들의 위치 (x,y)가 주어진다.(-1,000,000≤x,y≤1,000,000)

출력

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

# 접근 방법

• 모든 고객들의 편의점까지 거리의 합이 최소가 되어야 한다.
• 즉, 중간 점을 찾는 문제이기 때문에 입력받은 사람들의 위치를 X좌표, y좌표를 따로 저장해준다.
  • 이후 정렬을 하
  • 각각의 N//2번째 위치에 존재하는 값이 중간 값이 된다.

import sys  
input = sys.stdin.readline  

N = int(input())  
locx = []  
locy = []  
for _ in range(N):  
    a, b = map(int, input().split())  
    locx.append(a)  
    locy.append(b)  
locx.sort()  
locy.sort()  
mid = (locx[N//2], locy[N//2])  
result = 0  
for i in range(N):  
    result += abs(mid[0] - locx[i]) + abs(mid[1] - locy[i])  
print(result)