이분탐색/삼분탐색 #2110: 공유기 설치 [JAVA]

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

 

 

---

 

 

 

 

문제 접근

 

 

 

 

이분 탐색 upper bound를 어떻게 적용해야할지 몰라 블로그 글을 찾아봤다. 글을 보니까 이해는 되지만.. 실전 코테에서 내가 그 아이디어를 떠올릴 수 있을까 의문이다. 꾸준히 하다보면 늘겠지..

 

 

 

 

 

인접 공유기 간의 최소 거리가 있다고 하면 그 거리에 따라 설치할 수 있는 공유기의 개수가 정해진다. (약간 역발상..)

 

이때, 최소 거리가 클수록 설치할 수 있는 공유기의 개수는 줄어들고 최소 거리가 작을수록 공유기의 개수가 늘어난다.

 

 

우리가 구해야하는 인접 공유기 사이 최대 거리는 문제에서 주어진 공유기의 개수를 만족하는 최소거리의 최댓값을 구하면 된다. 따라서, upperbound를 활용해야한다. 

 

 

 

 

 

 

[ 참고 ] https://st-lab.tistory.com/277

 

 

 

 

 

 

 

 

코드

 

 

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());

		int[] home = new int[n];

		for (int i = 0; i < n; i++) {
			home[i] = Integer.parseInt(br.readLine());
		}

		Arrays.sort(home);

		System.out.println(upperBound(c, home) - 1);

	}

	static int upperBound(int c, int[] home) {
		int lo = 1; // 공유기 사이 최소 거리의 최솟값
		int hi = home[home.length - 1] - home[0] + 1; // 공유기 사이 최소 거리의 최댓값+1

		while (lo < hi) {
			int mid = (lo + hi) / 2;

			if (c <= canInstall(mid, home)) {
				lo = mid + 1;
			} else {
				hi = mid;
			}
		}
		return hi;
	}

	static int canInstall(int len, int[] home) {
		int cnt = 1;
		int lastIndex = home[0]; //첫 번째 집은 공유기가 반드시 설치되어 있어야한다.

		for (int i = 1; i < home.length; i++) {
			if (home[i] - lastIndex >= len) {
				cnt++;
				lastIndex = home[i];
			}
		}
		return cnt;
	}
}

 

 

 

 

여기서 첫 번째 집에 공유기를 반드시 설치해야하는데 왜냐면

 

 

 

 

 

이런 식으로 집이 설치되어 있고 공유기를 2개 설치해야한다 하자.

 

 

이때 제일 처음 집인 0에 공유기를 설치하지 않으면 5~9 사이에 공유기 2개를 설치해야하므로 인접 공유기 사이 최대 거리가 줄어든다. 반면, 0에 설치하면 0~9 사이에 공유기 2개를 설치할 수 있으므로 최대 거리가 늘어나기 때문에 제일 처음 집에는 공유기를 설치해야한다.