편의점 2 [백준 14400] - python

import sys
input = sys.stdin.readline

def BOJ14400():
  n = int(input())
  l = []
  a = []
  b = []
  for _ in range(n) :
    x, y = list(map(int, input().split()))
    a.append(x)
    b.append(y)
    l.append([x,y])
  a.sort()
  b.sort()
  x_median = a[len(a)//2]
  y_median = b[len(b)//2]
  
  result = 0
  for x, y in l :
    result += abs(x-x_median) + abs(y-y_median)
  print(result)
BOJ14400()

 

접근 방법 :

  1. 두 위치의 거리는 맨하탄 거리로 구한다. 
거리합을 최소로 하는 위치에 편의점을 위치시켜야 한다면 중위값에 위치시키는 것이 거리합의 최솟값을 구할수 있을것이라 판단하였다.

 

=> 절댓값을 더하게 되므로 크거나 작게 된다면 결국 결과값은 커진다.

고객이 위치한 점에 위치시켜야 0으로 만들어 줄수 있어 결과값 자체를 최솟값으로 만들수 있다고 판단하였다.

 

 

 

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

14400번: 편의점 2