JOYFUL's Devlog
/
Data Structure & Algorithm
/
안테나
Search
Share
안테나
문제 : 안테나
18310번: 안테나
문제 일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다. 이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다.
풀이
해결에 필요한 핵심 아이디어:
중간점!
해결 시나리오
•
모든 지점과의 거리합이 최소인 지점은
중간점!
◦
주어진 리스트의 요소를 정렬을 했을 때,
중간 인덱스의 요소를 선택
하는 게 베스트
▪
요소의 갯수가 홀수 → 정확히 중간점을 선택
▪
요소의 갯수가 짝수 → 중간 즈음에 있는 두 요소 중 아무거나 하나 선택
풀이
나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.
나동빈, 『이것이 취업을 위한 코딩테스트다 with 파이썬』, 한빛미디어(2020)
(이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬