공유기 설치(이분 탐색, 그리디)

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

2110번: 공유기 설치

 

도대체 어느 부분에서 이분 탐색을 해야하는건가 했는데

'간격'의 탐색에서 이분 탐색을 활용하여 점점 좁혀나가는 문제였다.

 

공유기를 설치할때 앞에서부터 탐색하여 목표하는 간격값을 넘어가면 바로 공유기를 설치한다

→ 그리디

설치한 공유기 갯수와 목표 공유기 갯수를 비교하여 이분탐색으로 목표 간격값을 최대한 늘려나간다

→ 이분 탐색

 

1. 중간 간격값을 설정한다((최소 간격 + 최대 간격) / 2)

※ 처음 최소 간격은 1, 최대 간격은 (처음 집 - 끝의 집)

2. 해당 간격으로 처음 집부터 공유기를 설치하여서 공유기를 몇 개 설치할 수 있는지 확인해 본다.

※ 최소 간격이 최대가 되기 위해선 어차피 처음 집에는 무조건 공유기가 설치되어야 함에 유의

3. 설치된 공유기와 목표 공유기에 따라서 

  3-1. 설치된 공유기가 목표치보다 적다면 간격을 좁힌다.(최대 간격 = 중간 간격 - 1) 

  3-2. 설치된 공유기가 목표치보다 많다거나 같다면 간격을 넓힌다.(최소 간격 = 중간 간격 + 1)

4. 최소 간격이 최대 간격을 넘어갈때까지 1~3항을 반복한다.

→조건(설치 수)을 만족하는 최대 간격을 이분 탐색

 

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

int N, C;
vector<int> Home;

int Solve(int mid)
{
	int ret = 1;
	int pre = Home[0];
	for (int i = 1; i < Home.size(); i++)
	{
		if (Home[i] - pre >= mid)
		{
			ret++;
			pre = Home[i];
		}
	}
	return ret;
}

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

	cin >> N >> C;
	int cmd = N;
	while (cmd--)
	{
		int tmp;
		cin >> tmp;
		Home.push_back(tmp);
	}
	sort(Home.begin(), Home.end());

	int ret = 0;
	int s = 1;
	int e = Home.back() - Home.front();
	while (s <= e)
	{
		int mid = ((s + e) / 2);
		if (Solve(mid) < C) e = mid - 1;
		else
		{
			ret = max(ret, mid);
			s = mid + 1;
		}
	}

	cout << ret;
}