[BOJ]2110-공유기 설치

2110

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

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

	int N{ 0 };
	int C{ 0 };
	int cnt{ 0 };
	int res{ 0 };
	
	cin >> N >> C;

	int* loc = new int[N];

	for (int i = 0; i < N; i++)
	{
		cin >> loc[i];
	}

	sort(loc, loc + N);
	int start = 1;
	int end = loc[N-1] - loc[0];

	while (start <= end)
	{
		cnt = 1;
		int middle = (start + end) / 2;
		int flag = loc[0];

		for (int i = 1; i < N; i++)
		{
			if (loc[i] - flag >= middle)
			{
				cnt++;
				flag = loc[i];
			}
		}

		if (cnt >= C)
		{
			if (middle > res)
			{
				res = middle;
			}
			start = middle + 1;
		}
		else
		{
			end = middle - 1;
		}

	}

	cout << res;
}

풀이를 생각하기 어려운 문제.

먼저 간격을 정하고 집들을 정렬한 뒤 왼쪽 집부터 차례대로 공유기를 설치한다.

그리고 설치된 공유기의 개수와 제공된 공유기의 값을 비교해 간격을 이분 탐색으로 조정해나가 최대 값을 정한다.

참고자료

2110 c++ 풀이