백준_18310_안테나 (python)

★ 접근

 N의 최대 크기를 이십만으로 제한했기 때문에 모든 경우를 다 탐색할 경우 시간초과가 나올 것이라 생각했다. 그래서 그리디로 접근해보자고 생각을 했다.

 

★ 풀이

 처음에는 모든 집에 대해서 안테나 거리들의 합이 최소일라면 가운데에 있으면 되는 것이 아닌가 했다. 너무 간단하다고 생각을 했고 코드도 너무 짧을 것 같아 확신이 없었다. 결국 다른 방법으로 해봤는데 틀렸다. 설마하고 첫 생각대로 해봤는데 통과돼서 허무했다.

 

import sys
input = sys.stdin.readline

N = int(input())
house = list(map(int,input().split()))

house.sort()
print(house[(N-1) // 2])