[백준/c++] 2110번: 공유기 설치

문제 링크

아이디어

설명

첫번째 집에는 반드시 하나의 공유기가 설치되어 있어야 한다.

2 3
5
15
18

의 테스트 케이스가 있다고 하자

#1

처음에 간격은 9이 될 것이다.
5번 집에 공유기 한대를 설치하고
15번 집에 가서 또 한 대를 설치한다.
그다음 15번 집에 설치된 공유기와 그 전/후에 설치된 공유기의 간격이 최소 9이 되어야 하나 그러지 못하기 때문에 간격을 줄일 필요가 있다.
결국 공유기를 설치하지 못하고 모든 집을 방문했으니 right를 mid-1로 조정한다. (간격 좁히기)

#2

간격은 4이 된다. (left = 0, right = 8)
5번 집에 이미 한대가 설치되어있고,
15번 집에 가서 한대를 설치한다.
15번과 18의 간격이 3이기 때문에 18번 집에 공유기를 설치할 수 없다.
그러므로 간격을 줄여야 한다.

#3

간격은 3 (left = 0, right = 3)
이제는 간격이 3이기 때문에 5번, 15번, 18번의 집에 공유기 총 3대를 설치할 수 있다.
일단 정답을 3으로 가정해두고 간격을 늘려본다. (최대 간격을 찾는 문제이기 때문에)
현재 테스트케이스의 경우 범위가 좁기 때문에 이대로 끝날 것이다.

문제에서 제공한 테스트 케이스

5 3
1
2
8
4
9

제출 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);

	int n, c;
	cin >> n >> c;
	int input;
	vector<int> v;

	for (int i = 0; i < n; i++)
	{
		cin >> input;
		v.push_back(input);
	}

	sort(v.begin(), v.end());

	int left = 0; 
	int right = v.back(); 
	int ans = -1;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		int beforeSetIdx = 0;  // 공유기를 놓은 첫번째 집
		int cnt = 1; // 첫번째 집에 설치된 공유기

		for (int idx = 1; idx < n; idx++)
		{
			if (v.at(idx) - v.at(beforeSetIdx) >= mid)
			{
				beforeSetIdx = idx;
				cnt++;
			}
		}

		if (cnt >= c)  
		{ // 간격 늘리기
			ans = mid;
			left = mid + 1;
		}
		else // 간격 좁히기
			right = mid - 1;
	}

	cout << ans;

	return 0;
}