BOJ 18310 안테나 문제 중간값 간단 증명

풀이 과정

백준 18310번 문제 링크

중간값이 답이란 느낌은 빡 왔지만…
머리속에서 확신이 들지 않아서,
완전탐색으로 풀었다. 아니나 다를까 시간초과였다.
(N이 2e^5에 시간제한 1초인데, for-loop가 2개 나올때부터 예상하긴 했다.)

답안을 봤더니 아주 간단하게 중간값을 선택하면 된다고 했다.
손으로 그려보다보면 이해한다고 한다.

그래서 그려봤다.
(머리로만 해서는 이해가 안되더라 ㅜㅜ)

간단 증명

중간값이 2개인 경우(n이 홀수)

중간값이 1개인 경우(n이 짝수)

보다시피 중간값에서 양 옆으로 이동할수록,
더해야 할 거리값의 갯수가 절대적으로 증가한다.

답

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

# 중간값 (medium)을 출력
print(data[(n - 1) // 2])

시간초과 코드

시간복잡도가 O(N^2)이므로 당연하게… 시간초과.

n = int(input())
data = list(map(int, input().split()))
data.sort() # 정렬할 필요가 없는 풀이 방법이었다 ...

INF = int(1e9)
min_val = INF
min_house = INF

for x in data: # O(N)
    tmp_val = 0
    for i in data: # O(N)
        if i == x:
            continue
        tmp_val += abs(i - x)

    if min_val > tmp_val:
        min_val = tmp_val
        min_house = x

print(min_house)