[BJO] 18310번

문제

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

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

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

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

입력

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

출력

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

예제 입력 1 

4
5 1 7 9

예제 출력 1 

5

 

 

Try1)

사실 이 문제는 코드짜기가 어려웠다기보단 문제 자체를 잘못 이해해서 의사코드 쓰기가 감이 안잡혔던 문제이다.

핵심은 '평균'이 아닌 '중간값'을 구하는 것이다.

계속 평균값으로 생각해서 만약 집이 1,1,1,1,1,1,1,10 정도 있다면 5에 안테나를 두는것보다 1에 두는게 낫지않나..?

평균값이 답이 안될수도 있지않나..?

했는데 다시보니 안테나는 집에만 설치할 수 있으므로 무조건 정렬 후 중간값에 설치하는 것이 이득이다.

중간값이 아닌 곳으로 안테나를 옮긴다면 무조건 더 멀어지는 집이 생길 수 밖에 없기 때문이다.

이 포인트를 파악하고 나서는 코드 짜는건 어렵지 않았다.

 

n=int(input())

house=list(map(int,input().split()))
house.sort()

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

 

 

++) 명확하게 중간값을 구해야만 하는 논리를 정리해주는 답변인 것 같아 추가