2110번 공유기 설치

문제링크 : www.acmicpc.net/problem/2110

2110번: 공유기 설치

---

---

<알고리즘>

1) 집들 간의 거리에서 가장 작은 값을 left, 가장 큰 값을 right로 놓는다.

2) middle = (left+right)/2 는 집들 간의 거리를 나타내고 함수를 이용해 해당 집들의 배열에서 최소 middle씩만큼 떨어뜨려 공유기 설치가 가능한지 확인

   2-1) 설치가 가능하다면, 그 값을 임시로 저장. &  left = middle+1로 범위를 변경한다.

   2-2) 설치가 불가능하다면 right = middle-1로 범위를 변경한다.

3) left<=right인 동안 2번을 반복해서 확인.

4) 앞서 2-1을 통해 저장해 놓은 값을 출력(마지막에 저장된 값이 가능한 값중 가장 큰 값.)

 

 

 

메모리 : 2804KB     시간 : 64ms

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

bool point(vector<int> home, int C, int middle) {
	int cnt = 1;
	int before = home[0];
	for (int i = 1; i < home.size(); i++) {
		if (home[i] - before >= middle) {
			cnt += 1;
			before = home[i];
		}
	}
	if (cnt >= C) {
		return true;
	}
	return false;
}
int main() {
	int N = 0;
	int C = 0;
	cin >> N >> C;

	vector<int>home(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> home[i];
	}
	sort(home.begin(), home.end());

	int left = 1;
	int right = home[N - 1] - home[0];
	int middle = 0;
	int result = 0;
	while (left <= right) {
		middle = (left + right) / 2;
		if (point(home, C, middle)) {
			result = max(result, middle);
			left = middle + 1;
		}
		else {
			right = middle - 1;
		}
	}

	cout << result;

	return 0;
}