[백준] 1477 휴게소 세우기

문제

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.

일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.

입력

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

출력

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, M, L, arr[200];
ll check(ll k) {
	int temp = 0, cnt = 0;
	for (int i = 0; i < N; i++) {
		if (arr[i] - temp > k) {
			temp += k;
			i--;
			cnt++;
		}
		else
			temp = arr[i];
	}
	while (temp+k < L) {
		temp += k;
		cnt++;
	}
	return cnt;
}
int main() {
	cin >> N >> M >> L;
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	
	sort(arr, arr + N);
	ll le = 1, ri = L - 1, mid, ans;
	while (le <= ri) {
		mid = (le + ri) / 2; 
		if (check(mid)<=M) ri = mid - 1,ans = mid;
		else le = mid + 1;
		
	}
	cout << ans;
}

 

M개의 휴게소를 더 지어서 가장가까운 휴게소간 거리의 최댓값 K를 구하자

만약 가장가까운휴게소간 거리가 P라면 M개의 휴게소를 지을 수 있을까 ?

조건: 휴게소간 가장 가까운 거리가 P일때 최소한 몇개이상의 휴게소를 지어야할까?

>>이분탐색