백준 1477번 휴게소 세우기

휴게소 세우기

2 초

128 MB

2299

958

697

41.988%

문제

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

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

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

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

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

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 같은 정수이다. 모든 휴게소의 위치는 중복되지 않으며, N+M은 L보다 작다. 둘째 줄에, 휴게소의 위치가 공백을 사이에 두고 주어진다.

출력

이 문제가 요구하는것 휴게소 m개를 모두지어 휴게소가 없는 구간의 길이의 최댓값의 최소값을 출력하라는 것이다. 
최댓값의 최소값을 구하기 위해선 당연히 현재 지어진 휴게소들의 거리중 최댓값을 일단 구해야한다.

최댓값을 구한후 그 거리를 이분탐색으로 거리를 나누며 그 횟수가 우리가 세우려는 m 값과 같은지 확인하여 답을 찾아낸다

#include <iostream>
#include <algorithm>
using namespace std;

int rest[102];
int n, m, k;

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> k;

	for (int i = 1; i <= n; ++i) {
		cin >> rest[i];
	}
	rest[n + 1] = k;
	sort(rest, rest + n + 1);

	int first = 1, end = k - 1;
	while (first <= end) {
		int cnt = 0;
		int mid = (first + end) / 2;
		
		for (int i = 1; i <= n + 1; ++i) {
			if (rest[i] - rest[i - 1] > mid) {
				cnt += (rest[i] - rest[i - 1] - 1) / mid;
			}
		}
		if (cnt > m) {
			first = mid + 1;
		}
		else {
			end = mid - 1;
		}
	}

	cout << first << endl;
	return 0;
}