[C++] 마구간 정하기 🔥

📄문제

N개의 마구간이 1차원 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다.
각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.
C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.

 

⬇️ 입력

첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 한 줄에 하나씩 주어집니다.

5 3 1 2 8 4 9

 

⬆️ 출력

줄에 가장 가까운 두 말의 최대 거리를 출력하세요.

3

 

📝 풀이

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

bool trySetHorse(vector<int> arr, int c, int gap)
{
	int i = 0;
	int n = arr.size(); // 마구간의 개수

	// 첫번째 말은 0번에 배치하도록
	--c;

	for (; i < n - 1; ++i)
	{
		for (int j = i; j < n - 1; ++j)
		{
			if (arr[j + 1] - arr[i] >= gap)
			{
				i = j + 1;
				--c;
			}

			if (c == 0)
				return true;
		}
	}

	return false;
}

int main()
{
	int N, C;
	scanf_s("%d %d", &N, &C);

	vector<int> arr(N);

	for (int i = 0; i < N; ++i)
		scanf_s("%d", &arr[i]);
	sort(arr.begin(), arr.end());

	int lt = 1, rt = arr[N - 1], mid;
	int res = 0;

	while (lt <= rt)
	{
		mid = (lt + rt) / 2;

		bool isSuccess = trySetHorse(arr, C, mid);

		if (isSuccess) // 말 배치에 성공하였다면?
		{
			res = mid;
			// lt를 올려 최대 거리를 늘리기
			lt = mid + 1;
		}
		else // 말 배치에 실패하였다면?
		{
			// rt를 줄여 최대 거리를 줄이기
			rt = mid - 1;
		}
	}

	printf("%d", res);
}

• '[C++] 뮤직비디오 🔥' 문제와 마찬가지로 이분검색 알고리즘을 응용하여 lt, rt, mid를 사용하여 문제를 해결합니다.
• mid 값은 말 사이의 최소 거리로, 첫번째 말부터 시작하여 말을 둘 수 있는지 검사합니다.
• 말을 충분히 두었다면, mid를 늘려 gap을 올리며 말 사이의 최소 거리를 늘려서 최적의 답을 찾아갑니다.