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

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

2110번: 공유기 설치

이분 탐색을 통해 두 공유기 사이가 최소 특정 거리 이상으로 배치해서 공유기를 모두 배치할 수 있는지 판단하는 방법으로 문제를 해결했다.

 

코드

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

int n, c;
vector<int> x;

//두 공유기 사이가 최소 dist 이상으로 만들 수 있는지 확인
bool Solve(int dist) {

	int check = 0;
	int cnt = 0;

	for (int i = 0; i < x.size(); i++) {

		if (x[i] < check)
			continue;

		cnt++; //x[i]위치에 공유기 설치
		check = x[i] + dist; //다음 공유기 위치는 해당 위치보다 dist이상에 있어야 한다
	}

	if (cnt >= c)
		return true;

	return false;
}

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

	cin >> n >> c;

	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;

		x.push_back(input);
	}

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

	int left = 0;
	int right = 1000000000;
	int mid;
	int result = -1;

	while (left <= right) {

		mid = (left + right) / 2;

		if (Solve(mid))
		{
			result = mid;
			left = mid + 1;
		}

		else
			right = mid - 1;
	}

	cout << result;

	return 0;
}