[백준 1477] 휴게소 세우기 (C++)

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

1477번: 휴게소 세우기

문제

---

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

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

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

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

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

 

입력

---

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

 

출력

---

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

 

제한

---

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

 

문제 풀이

---

이분 탐색 문제. 휴게소가 없는 구간의 최댓값을 mid로 두고, 해당 간격을 최대로 하게끔 각 휴게소 사이, 고속도로 끝점과 첫 휴게소 사이, 고속도로 끝점과 마지막 휴게소 사이에 몇 개 휴게소를 설치할 수 있는지 확인한다.

만약 최대 간격이 mid일 때 휴게소를 M개 설치할 수 있다면 더 작은 값을 가질 수 있는지 확인하기 위해 right를 mid-1로 설정하여 범위를 줄인다.

만약 최대 간격이 mid일 때 휴게소를 M개보다 더 많이 설치하게 된다면 최대 간격이 너무 좁은 것이므로 left를 mid+1로 설정하여 범위를 줄인다.

만약 최대 간격이 mid일 때 휴게소를 M개보다 더 적게 설치하게 된다면 최대 간격이 너무 넓은 것이므로 right를 mid-1로 설정하여 범위를 줄인다. 단 최대 간격이 mid가 되도록 일부만 세우고 나머지는 간격을 그것보다 더 줄여서 M개가 되도록 맞출 수 있으므로 mid도 정답이 될 수 있다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;
int* arr;
int* distArr;
int N, M, L;
int minAnswer = 0;

void binarySearch(int left, int right)
{
	minAnswer = L;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		int counts = 0;
		for (int i = 0; i < N+1; i++)
		{
			if (distArr[i] > mid)
			{
				counts += distArr[i] / mid;
				if (distArr[i] % mid == 0)
				{
					counts--;
				}
			}
		}
		if (counts <= M)
		{
			right = mid - 1;
			minAnswer = min(mid, minAnswer);
		}
		else
		{
			left = mid + 1;
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N>>M>>L;
	arr = new int[N];
	distArr = new int[N + 1];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	distArr[0] = arr[0];
	for (int i = 1; i < N; i++)
	{
		distArr[i] = abs(arr[i] - arr[i - 1]);
	}
	distArr[N] = L - arr[N - 1];
	binarySearch(1, L);
	cout << minAnswer << "\n";
	return 0;
}