[백준 18310] 파이썬 : 안테나

18310

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

18310번: 안테나

[정답]

import sys
N = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
a.sort()
print(a[(N-1)//2])

.

.

.

[풀이]

중앙값을 구하는 문제이다. 중앙값 중에서도 최솟값을 구해야 하기 때문에 (N-1)//2를 해준다

 

처음에는 중앙값이 답인줄 모르고 모든 안테나 에서의 거리 중 최소를 구하는 완전탐색을 했다.

import sys
N = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
a.sort()
for n in range(N-1, -1, -1):
    total = 0
    total += a[n]*n - sum(a[:n]) 
    total += sum(a[n:]) - a[n]*(N-1-n)
    if n == N-1:
        t_result = total
    t_result = min(t_result, total)
    if t_result == total:
        result = a[n]
print(result)
#오답

그 결과 시간초과가 떴다.

고민하면서 풀며 설마... 했는데

답이 중앙값이라 어이가 없었다.