백준 | 안테나

백준 안테나

문제

일직선 상에 위치한 집 n개의 위치가 주어질 때, 안테나(어떤 한 집에 설치)로부터 모든 집까지의 거리 총합이 최소가 되는 위치를 찾는 문제이다.

추가로 안테나를 설치할 수 있는 위치 값이 여러 개일 경우, 가장 작은 값을 출력해야 한다.

풀이

그림을 그려보면 모든 집까지의 거리 총합이 최소가 되는 위치는, 주어진 위치 n개의 중간값임을 알 수 있다.

n이 짝수인 경우는 n // 2 - 1, n // 2에서의 거리 총합이 같은데, 조건에 의해 둘 중 작은 값이 정답이므로 n // 2 - 1의 위치를 출력하면 된다.

코드

# 안테나

import sys


# 입력
n = int(sys.stdin.readline())
locations = list(map(int, sys.stdin.readline().split()))

# 정렬
locations.sort()

# 출력
if n % 2 == 1:
    print(locations[n // 2])
else:
    print(locations[(n // 2) - 1])