[백준] 2110 공유기 설치 (이분탐색) C++

www.acmicpc.net/problem/2110

 

• dfs 조합으로 풀었는데 실패가 뜸...

• 집의 좌표가 엄청 길다... 이분탐색으로 풀어야함. !!!!!!

• 간격 표

  • low는 간격 1, high는 간격 9 (사실상 최대 간격은 9-1=8이다.)
  • mid는 간격 조절 ex) mid =5 이면 cnt가 2다 (집간의 간격을 5로 두면 공유기를 설치 할 수 있는 갯수는 2개다.)
    • mid 간격 조절을 다시한다.(1) 간격이 너무 커서 공유기 설치 갯수가 2개 밖에 안나오니깐 간격을 줄인다.
      • right = mid -1;
    • mid 간격 조절을 다시한다.(2) 반대로 간격이 너무 좁아서 갯수가 3을 초과한다.
      • left = mid + 1;

low	1	1	3	4
high	9	4	4	4
mid	5 (간격이 5 이상이면 cnt++해준다)	2	3	end
cnt	2	3	3	end
answer	X	2	3	3

• 공유기가 설치된 집의 간격 >= mid 이상일 경우 cnt++ 해준다
  • cnt++이 공유기의 최소갯수보다 크면 답이 될 후보이다.
• C++ 코드
  • 왜 Left가 1부터 시작인지는 모르겠음.. house[0]은 실패뜸...

#include <iostream>

#include <algorithm>

/*
5 3
1
2
8
4
9
*/
using namespace std;
int n, m;
int house[200000];
bool solution(int mid)
{
	int cnt = 1;
	int now = house[0];
	//cout << "mid:" << mid << endl;
	for (int i = 1; i < n; i++)
	{
		if (house[i] - now >= mid)
		{
			cnt++;
			now = house[i];
			//cout << "mid:" << mid << endl;
			//cout <<"now:" <<now << endl;
		}
		//cout << "cnt:" << cnt << endl;

	}
	if (cnt >= m)
		return true;
	return false;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> house[i];
	}
	sort(house, house + n);
	//for (int i = 0; i < n; i++)
	//	cout << house[i] << " ";
	//int Left = house[0];
	int Left = house[0];
	int mid;
	int right = house[n - 1] - house[0];

	int result = 0;
	//cout <<"right : " <<right << endl;
	while (Left <= right)
	{
		//cout << "Left : " << Left << endl;
		//cout << "right : " << right << endl;
		mid = (Left + right) / 2;

		if (solution(mid))
		{
			result = max(result, mid);
			Left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}

	}

	cout << result << endl;


	return 0;
}