문제

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

---

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄이다.

---

출력

첫째 줄에 M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.

---

풀이

제한조건

• 0 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• 100 ≤ L ≤ 1,000
• 1 ≤ 휴게소의 위치 ≤ L-1
• N+M < L
• 모든 휴게소의 위치는 중복되지 않음
• 입력으로 주어지는 모든 수는 정수

접근방법

이분탐색

새로 지을 수 있는 휴게소의 수가 1개가 아니기 때문에,
단순하게 접근하면 너무나 많은 경우의 수가 나온다.
어떤 경우에서는 두 휴게소 사이에 2개 이상을 새로 짓는것이 이득인 경우도 있기 때문이다.

따라서 이분탐색을 통해서 거리를 계산해보자.
이분 탐색을 통해서 찾고자 하는 값은 두 휴게소 사이의 거리 최솟값이다.

문제의 예시로 생각해 보자.

3 1 1000
200 701 800

고속도로의 시작과 끝에도 휴게소가 있다고 생각해야한다.
따라서 없는 구간의 길이만 살펴보게 된다면 아래와 같다.

구간1			구간2		구간3			구간4
199		-	500		-	98	 	-	199
(0~200)	(200~701) 	( 701~800) 	(800~1000)

만약, 구하고자 하는 휴게소 사이의 길이(최댓값의 최솟값)를 ((1+1000-1) / 2)500으로 가정해보자.
구간 1,3,4에는 들어갈 수 없고, 구간 2에는 가능하다.
1개를 짓는 조건에는 부합하지만 최적의 값은 아니다.

이제 다시 반으로 더 줄여보자.
(1+500)/2) 250 이라고 생각해보자.
구간 1,3,4에는 여전히 설치할 수 없고, 구간 2에는 2개 설치가능하다.
여기서는 조건에 부합하지 않으므로, 다시 또 조절한다.

생각해보면 위의 과정이 반복되며, 이 과정이 전형적인 이분탐색 과정이다.
left와 right를 적절히 조절해가며, 마지막 까지 조건을 만족시키는 mid값을 구한다면,
문제에서 요구하는 최댓값의 최솟값을 구할 수 있다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
	static int N, M, L;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String[] inputs = in.readLine().split(" ");
		N = stoi(inputs[0]);
		M = stoi(inputs[1]);
		L = stoi(inputs[2]);

		List<Integer> list = new ArrayList<>();
		inputs = in.readLine().split(" ");
		for (int i = 0; i < N; ++i)
			list.add(stoi(inputs[i]));

		list.add(0);
		list.add(L);
		Collections.sort(list);

		// 긱 휴게소 간 거리만을 저장한다.
		List<Integer> diff = new ArrayList<>();
		for (int i = 0; i < N + 1; ++i)
			diff.add(list.get(i + 1) - list.get(i) - 1);

		// 이분탐색으로 휴게소와 휴게소 사이의 적당한 거리를 찾아보자.
		int left = 1;
		int right = L - 1;

		while (left <= right) {
			int mid = (left + right) / 2;

			// 각각의 구간 사이에 몇개를 설치할 수 있는지 찾는다.
			int count = diff.stream()
				.mapToInt(i -> i / mid)
				.sum();

			if (count > M)
				left = mid + 1;
			else
				right = mid - 1;
		}
		System.out.println(left);
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}