공유기 설치
[백준] 2110번 공유기 설치 (feat.Binary Search)이분 탐색
[백준] 2110번 공유기 설치 (feat.Binary Search)이분 탐색
2022.05.05https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 접근 문제에서 주어진 x의 좌표 범위를 봤을 때, 이분탐색으로 문제풀이를 접근해야 한다고 생각한다. 그렇다면 어떤 것을 이분탐색 해야할까? 문제의 핵심은, 공유기 사이의 좌표 간 거리중에 C개의 공유기를 설치할 수 있는 최대거리를 구하는 것이다. 즉, 공유기 사이의 거리로 가능한 최소와 최대를 정하여 해당 범위를 이분탐색 해야한다. 특정 거리를 ..