(c++)백준 2110번: 공유기 설치

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

2110번: 공유기 설치

[풀이]

이분탐색으로 풀 수 있었다.

먼저 입력으로 받은 집의 좌표들을 정렬하고, low는 1, high는 가장 처음 집과 가장 마지막 집의 거리로 설정하였다.

 

#include <iostream>
#include <algorithm>
using namespace std;
#define Max 200001

int N, C;
int Home[Max];

bool Share(int dist) {
	int cnt = 1;
	int phome = Home[0];
	for (int i = 1; i < N; i++) {
		if (Home[i] - phome >= dist) {
			phome = Home[i];
			cnt++;
		}
	}
	if (cnt >= C)
		return true;
	return false;
}

void solution() {
	cin >> N >> C;
	int Maxdist = 0;
	
	for (int i = 0; i < N; i++) {
		cin >> Home[i];
	}
	sort(Home, Home + N);
	
	int high = Home[N-1] - Home[0];//가장 마지막 집과 처음 집의 거리 차이
	int low = 1;

	//low ~ high 거리 중에 공유기 C개 설치할 수 있으면서 가장 긴 두 공유기 사이 거리 찾기
	while (low <= high) {
		int mid = (low + high) / 2;
		//각각 인접한 집들이 모두 mid 이상으로 떨어져 있으면
		if (Share(mid)) {
			Maxdist = max(Maxdist, mid);
			low = mid + 1;
		}
		else
			high = mid - 1;
	}
	cout << Maxdist << endl;
}

int main() {
	solution();
	return 0;
}