[C++] 백준 2110번 - 공유기 설치

 

 

문제 2110번

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

2110번: 공유기 설치

 

이번 문제는 내가 잘못 생각했다. 최대 거리를 구해야하니까 거리를 기준으로 잡아야 하는데 나는 공유기에 집중했다. 그래서 start와 end에는 각각 최소와 최대 거리를 넣어준다. 그리고 1부터 N까지 반복문을 사용하여 뺏을 때 거리가 mid보다 크거나 같은지 확인한다. 만약 크거나 같으면 공유기 개수를 count해주고 다음 공유기를 찾아야하니 temp는 현재 i값을 인덱스로 넣은 값으로 넣어준다. 그렇게 반복문이 끝나고 count가 공유기 개수 C보다 크거나 같은지 확인하여 mid랑 그동안 넣어놨던 거리를 비교하여 result에 넣는다. 그리고 start는 이전보다 넓은 거리를 사용하기 위해 1 증가해준다. 반대로 end는 좁은 간격을 사용하기 위해 1을 감소시켜준다. 그렇게 while문을 나오면 result에는 최대 거리가 나온다.

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

vector <int> v;
int N, C;

int main() {
	cin >> N >> C;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	int start = 1, end = v[N - 1] - v[0]; //최소, 최대 거리
	int count, temp, result = 0;
	while (start <= end) {
		int mid = (start + end) / 2;
		count = 1;
		temp = v[0];

		for (int i = 1; i < N; i++) {
			if (v[i] - temp >= mid) {
				count++;
				temp = v[i];
			}
		}
		if (count >= C) {
			result = max(result, mid);
			start = mid + 1;
		}
		else {
			end = mid - 1;
		}
	}
	cout << result;
	return 0;
}