[백준] 18310번 안테나 (by Python)

문제

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

18310번: 안테나

 

풀이

    무척 쉬워보이고, 코드 또한 4줄로 매우 간단하게 풀 수 있는 문제이지만 개인적으로 해답을 떠올렸음에도 확신하지 못해 많이 애먹은 문제이다. 결론적으로 답은 주어진 숫자들을 오름차순으로 정렬한 후의 가운뎃값이다. 어떻게 이 결론이 성립하는지 예시를 통해 알아보도록 하자.

    오름차순으로 정렬된 숫자 5개 (a, b, c, d, e)가 있고 a, b / b, c / c, d / d, e 의 거리를 각각 x_1, x_2, x_3, x_4라고 하도록 하겠다. 그럴 경우 안테나 위치에 따른 거리의 총합은 다음과 같다.

 

a: 4x_1 + 3x_2 + 2x_3 + x_4

b: x_1 + 3x_2 + 2x_3 + x_4

c: x_1 + 2x_2 + 2x_3 + x_4

d: x_1 + 2x_2 + 3x_3 + x_4

e: x_1 + 2x_2 + 3x_3 + 4x_4 

 

    x_1, x_2, x_3, x_4의 크기와 상관없이 가운뎃값일 때 가장 작은 총합을 보이는 것을 알 수 있다. 이에 따라 정렬 후 가운뎃값을 항상 선택할 수 있는 다음과 같은 코드를 짰다. (수가 짝수일 경우에는 문제 조건에 따라 가운데 두 개의 값 중 더 작은 값)

 

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

print(arr[(n - 1) // 2])