태그:
N개의 집에 C개의 공유기를 놓을 때 공유기 사이의 최소 거리의 최대값을 구하는 문제입니다. 이 문제는 어디서 이분 탐색을 써야할지 조금 고민되는 문제입니다. 바로 공유기의 최소 거리를 이분 탐색으로 찾습니다. 먼저 집의 위치를 정렬합니다. 그리고 최소 거리를 가정하여 이 거리를 바탕으로 공유기를 설치해보고, 이 때 설치할 수 있는 최대 공유기 개수를 구합니다. 이 공유기 개수가 C를 넘는지 여부에 따라 이분 탐색할 범위를 새로 지정합니다. 이렇게 찾은 거리를 출력하면 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-04-07 23:50:13 |