<백준 18310번-python> 안테나

풀이 시간 : 30분

시간 제한 : 1 초

메모리 제한 : 256 MB

출처 : 백준-18310번 https://www.acmicpc.net/problem/18310

문제

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

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

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

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

입력

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

출력

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

내가 적어본 문제 풀이

수직선 상에 위치한 집들을 정렬한 뒤, 중간값을 찾아 안테나를 설치하면 다른 집들과의 거리의 차의 합이 최소가 되는 간단한 문제다.

하지만 처음 접근할 때, 중복되는 집이 존재할 수 있다는 조건 때문에 중간값이 과연 최소가 될 수 있을까 하는 의문이 들었다. 그래서 고민하다가 모든 위치에서의 경우를 계산하는 완전 탐색으로 구현했다가 N의 최대값이 200,000이므로 당연히 실패했다.

결국 공책에 직접 그림을 그려가며 풀었는데 신기했지만 당연하게도 중간값이 최소가 되는 위치였다. 정확하게는 중간값이 될 수 있는 범위 안에서 최소가 되는 위치들이 존재하게 된다.

크게 두 가지로 나뉘는데,

• 홀수일 때

→ 정확하게 중간 값이 유일한 답

• 짝수일 때

→ 중간값이 2개가 나오는데, 위치상으로 왼쪽에 위치한 중간 집부터 오른쪽에 위치한 중간집까지를 포함하는 범위 안의 모든 위치가 최소가 된다. 이 때문에 문제에서

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

라는 조건을 준 것이다.(실제 1 3 3 3 6 6 7 9로 테스트 해보면 3,4,5,6이 모두 18로 같음을 확인 가능)

수학적으로도 죄,우 어디로 이동하든 중간 위치일 경우 왼쪽 집들의 개수와 오른쪽 집들의 개수가 같으므로 거리의 차의 합이 동일하게 +,- 된다.

그리고 실제 코드로는 위 두 경우를 굳이 나눌 필요없이 크기를 2로 나눈 몫을 이용하면 된다. 단, 이때 크기를 먼저 1로 뺴준다. 그 이유는 홀수일 때는 어차피 나머지가 1이므로 값이 같고, 짝수일 때 그냥 2로 나누면 오른쪽에 위치한 집의 값이 나온다.(6을 2로 나누면 3이니까) 따라서 다음에 -1을 해줘야 하는데 이러면 홀수일 때를 따로 또 분리해 줘야 하므로 애초에 크기보다 1 작은 값을 2로 나누면 해결되는 아이디어다.

n = int(input())
house_li = []
house_li = list(map(int, input().rstrip().split()))
house_li.sort()
print(house_li[(n-1)//2])

이런 쉬운 문제를 굳이 포스팅하는 이유는 수학적 감을 믿고(사실 실력이 딸려서 확실한 감이 안온 거겠지만) 간단한 예제를 실제로 해보자는 교훈을 기록하기 위함이다… 그리고 (n-1)//2 아이디어도 재밌었다.