29_공유기 설치 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ happenundo.tistory.com
공유기설치
2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이 문제는 N개의 집 중에, C개의 공유기를 설치하는 문제다. 단, C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 해야 한다. 시간 제한이 2초이고, 집의 좌표는 최대 10억이다. 그러므로 O(N) 시간으로는 불가능할 것이고, O(logN) 시간으로 풀어야 하겠다는 생각이 들었다. 그렇다면 이진 탐색인데, 이진 탐색을 어떻게 돌아야 할까? 그래서 이렇게저렇게 생각을 ..
