[백준(BOJ)] 18310번 안테나 - 파이썬/python

문제

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

 

일직선 상의 마을에 여러 채의 집이 위치할 때, 한 개의 안테나를 설치하기로 했다. 안테나로부터 모든 집까지의 거리의 총합이 최소가 되도록 설치할 위치를 구하는 문제다.

 

제한사항

• 첫째 줄에 집의 수 N(1≤N≤200,000)이 자연수로 주어진다. 
• 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다.

 

예시

Example 1:

Input: 4
5 1 7 9
Output: 5

 

풀이

집들의 위치를 오름차순으로 정렬한 후, 중앙값에 안테나를 설치하면 집들까지의 거리를 최소로 만들 수 있다.

n = int(input())
locations = list(map(int, input().split()))
locations.sort()

#중간에 위치한 집의 인덱스를 구하고 해당 위치 출력
print(locations[(n - 1) // 2])

• 집의 개수와 각 집의 위치를 리스트로 받는다.
• 집들의 위치를 정렬한다.
• 중간에 있는 집의 위치를 출력한다.