[백준] 18310. 안테나 (python)

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

18310번: 안테나

 

문제

일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다. 이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다.

집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오.

예를 들어 N=4이고, 각 위치가 1, 5, 7, 9일 때를 가정하자.

이 경우 5의 위치에 설치했을 때, 안테나로부터 모든 집까지의 거리의 총 합이 (4+0+2+4)=10으로, 최소가 된다.

입력

첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다.

출력

첫째 줄에 안테나를 설치할 위치의 값을 출력한다. 단, 안테나를 설치할 수 있는 위치 값으로 여러 개의 값이 도출될 경우 가장 작은 값을 출력한다.

풀이

N개의 집 중에서 안테나는 딱 한 집에만 설치한다.

안테나와 집들의 거리의 합의 최솟값을 구하는 문제인데,

처음 읽고 나서는 완탐으로 풀어야 되는 줄 알았다. 최솟값을 구하려면 모든 경우의 수를 구해서 그 중에서

최솟값을 구해야 정석이니까..? 근데 입력 조건에서 N이 최대 200,000이 될 수도 있다고 했다.

완탐으로 하면 O(N^2)이 나와서 200억이 된다. 시간 제한이 1초니까 완탐이 아니라는 소리다.

 

그럼 어떻게 최솟값을 구하지? 라고 생각해보다가 어떻게 되든 집들은 일직선 상에 놓여있고,

안테나를 집들이 골고루 쓰려면 가운데에 위치해야 한다. 

여러 예제를 만들어서 가운데가 아닌 경우도 있나 생각해봐도 찾지 못했다.

집들이 극단적으로 양 극단에 몰려 있다고 해도 그 중에서 가운데에 위치한 집에 설치해야 최소가 된다.

상식적으로 생각하면 당연한 건데, 예외가 있을 수도 있다는 생각에 모든 경우의 수를 살피는 것이 습관이 되서 자연스레 완탐 말고는 생각을 못했던 것 같다.

 

그래서 이 문제는 집들 중 가운데 위치한 집의 인덱스를 찾으면 끝나는 문제다!

집의 개수가 홀수일 때에는 가운데가 있지만, 짝수일 때에는 가운데가 2개다. 어떻게 계산해도 가운데 두 집의 안테나 거리의 합은 동일하게 나온다. 출력 조건 중 안테가 설치 위치가 여러 개면 작은 값을 출력한다고 했으므로

가운데 2개 중 앞의 집을 선택하면 된다.

그럼 집의 개수 N중에 선택해야 할 집의 위치는 (N-1)//2이다.

 

import sys
input = sys.stdin.readline
n = int(input())        # ~ 200,000
houses = list(map(int, input().split()))

houses.sort()
min_index = (n-1)//2
print(houses[min_index])

 

집들의 인덱스를 정렬한 뒤에 가운데 위치의 집을 찾아 출력한다.

 

알고리즘 분류

• 정렬