[백준] 2110 공유기 설치 [자바]

 

---

https://st-lab.tistory.com/277

[백준] 2110번 : 공유기 설치 - JAVA [자바]

https://www.acmicpc.net/board/view/74023

글 읽기 - 이분탐색 코드에서 왜 (count==C) 조건을 추가하면 안되는건가요?

https://www.acmicpc.net/board/view/68623

글 읽기 - 이분 탐색 조건

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	static int[] router;
	static int N;
	static int C;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		router = new int[N];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			router[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(router); //이분탐색 = 정렬
		
		int lo = 1; //최소거리
		int hi = router[N-1] - router[0] + 1; //최대거리도 탐색될 수 있게
		while(lo < hi) {
			int mid = (hi + lo) / 2; //거리
			
			if(canInstall(mid) >= C) { //설치된 공유기가 C(설치해야하는 공유기 수) 보다 크면
				lo = mid + 1; //최소 거리를 늘려준다
			}
			else {
				//hi = mid-1;
				hi = mid; //최소 거리를 줄여준다
			}
		}
		System.out.println(lo - 1);
	}
	static int canInstall(int n) {
		int count = 1;
		int start = router[0];
		for(int i = 1; i < N; i++) {
			int locate = router[i];
			
			if(locate - start >= n) { //최소 거리보다 크면
				count++; //공유기를 설치함
				start = locate; //공유기를 설치한 집 위치
			}
		}
		return count;
	}
}