정렬
-
[백준] 18310번 안테나 (by Python)Programming/Algorithm 2021. 3. 14. 15:28
문제 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 풀이 무척 쉬워보이고, 코드 또한 4줄로 매우 간단하게 풀 수 있는 문제이지만 개인적으로 해답을 떠올렸음에도 확신하지 못해 많이 애먹은 문제이다. 결론적으로 답은 주어진 숫자들을 오름차순으로 정렬한 후의 가운뎃값이다. 어떻게 이 결론이 성립하는지 예시를 통해 알아보도록 하자. 오름차순으로 정렬된 숫자 5개 (a, b, c, d, e)가 있고 a, b / b, c / c, d / d, e 의 거리를 각각 x_1, x..