Search

안테나

문제 : 안테나

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

풀이

해결에 필요한 핵심 아이디어: 중간점!

해결 시나리오

•
모든 지점과의 거리합이 최소인 지점은 중간점!
◦
주어진 리스트의 요소를 정렬을 했을 때, 중간 인덱스의 요소를 선택하는 게 베스트
▪
요소의 갯수가 홀수 → 정확히 중간점을 선택
▪
요소의 갯수가 짝수 → 중간 즈음에 있는 두 요소 중 아무거나 하나 선택
풀이

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.

Made with