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

 

14400번: 편의점 2

문제

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

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

 

문제풀이

n=int(input())
tmp=[]
for _ in range(n):
    tmp.append(list(map(int,input().split())))
#01
tmp.sort(key=lambda x:x[0])
mid_x = tmp[n//2][0]
#02
tmp.sort(key=lambda x:x[1])
mid_y = tmp[n//2][1]

ans=0
for i in tmp:
	#03
    ans+=abs(mid_x-i[0])+abs(mid_y-i[1])
print(ans)

- #01 : 입력받은 x 값 중에서 중앙값을 mid_x에 저장한다.

- #02 : 입력받은 y 값 중에서 중앙값을 mid_y에 저장한다.

- #03 : mid_x, mid_y에 편의점을 세우는 것이 가장 최소의 값이다.

           즉 mid_x, mid_y 값과 좌표들의 차이를 ans에 모두 더한 값이 정답이 된다.

           참고로 abs는 절대값을 의미하며, 음수 값이 나와도 최종적으로 양수 값으로 ans에 더한다.