• 아이디어는 [[binary-search]]{parametric-search} 이고, 이전 휴게소 위치에서 mid만큼 떨어진 곳에 휴게소를 세워갔을 때 M개 이하를 세울 수 있으면 해당 mid는 가능한 휴게소 없는 구간의 길이의 최댓값에 해당한다.
    • 그럼 해당 mid가 최솟값인지 확인한 후, mid보다 더 작은 값으로 가능한 지 여부를 확인해본다.
  • 기존 휴게소 배열 input에 양 끝단인 0과 L을 추가한다
  • 휴게소 없는 구간의 길이는 1(left)에서 input 사이 거리의 최댓값(right)까지 가능하다.
  • M개 이하를 세울수 있는지 여부를 확인하는 방법
    • 이전 휴게소 위치(lastPlace)에서 우측으로 mid만큼 떨어진 곳(placeToBuild)이 다음 휴게소(input[i])보다 좌측이면 해당 위치에 휴게소를 세우고(cnt–), 이전 휴게소 위치를 해당 위치로 갱신한다.
    • placeToBuild가 input[i] 보다 우측이면 휴게소를 세우지 않고, input[i]를 lastPlace로 갱신한다. 다음 휴게소도 갱신한다(i++).


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64



import java.io.*;
import java.util.*;

public class Main {
	static int N, M, L;
	static int[] input;

	static boolean possible(int mid) {
		int cnt = M;
		int lastPlace = input[0];
		int i = 1;
		while (i < N) {
			int placeToBuild = lastPlace + mid;
			if (placeToBuild < input[i]) {
				cnt--;
				lastPlace = placeToBuild;
			} 
			else {
				lastPlace = input[i];
				i++;
			}
		}
		return cnt >= 0;
	}

	static int solution() {
		Arrays.sort(input);
		int left = 1, right = 0;
		for (int i = 1; i < N; i++)
			right = Math.max(right, input[i] - input[i-1]);

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

			if (possible(mid)) {
				res = mid;
				right = mid - 1;
			}
			else
				left = mid + 1;
		}
		return res;
	}

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

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		N += 2;
		input = new int[N];
		input[0] = 0;
		input[1] = L;
		st = new StringTokenizer(in.readLine(), " ");
		for (int i = 2; i < N; i++)
			input[i] = Integer.parseInt(st.nextToken());

		System.out.println(solution());
	}
}