[BOJ 2110] 공유기 설치

📃 문제

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

2110번: 공유기 설치

---

💻 코드

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

int N, M;
int arr[200001];

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) cin >> arr[i];
	sort(arr, arr + N);

	int start = 1;
	int end = arr[N - 1] - arr[0];
	int mid = 0;
	int result = 0;

	while (start <= end) {
		mid = (start + end) / 2;

		int cnt = 1; // 배치된 공유기 개수
		int temp = 0;
		for (int i = 1; i < N; i++) {
			int len = arr[i] - arr[temp];
			if (len >= mid) {
				cnt++;
				temp = i;
			}
		}

		if (cnt < M) end = mid - 1;
		else {
			result = mid;
			start = mid + 1;
		}
	}
	cout << result << '\n';
}

 

메모리 및 시간

---

💡 풀이

 

가장 인접한 두 공유기 사이의 최대 거리를 구하는 문제이기 때문에 제일 첫번째 집에는 무조건 공유기를 설치할 것 → 최대 거리가 나올 수 있음

 

 

int cnt = 1; // 배치된 공유기 개수
	int temp = 0;
	for (int i = 1; i < N; i++) {
		int len = arr[i] - arr[temp];
		if (len >= mid) {
			cnt++;
			temp = i;
	}
}

 

temp는 마지막으로 공유기가 설치된 좌표가 저장된 인덱스

 

- 마지막으로 설치된 공유기 위치와 현재 집의 좌표를 비교하여 mid, 즉 최대거리로 가정한 거리보다 크거나 같으면 해당 집의 좌표에 공유기 설치가 가능

- 공유기 설치 후 temp 값은 마지막으로 설치된 공유기 좌표(i)로 갱신 및 설치된 공유기 개수(cnt)를 증가

 

if (cnt < M) end = mid - 1;
	else {
		result = mid;
		start = mid + 1;
}

 

- 설치하고자 하는 공유기 개수(M)보다 현재 최대 거리로 가정한 값(mid)에서 설치된 공유기 개수(cnt)가 더 작으면 거리를 줄인다

- cnt가 더 크면 result를 갱신하고 거리를 더 늘린 후 다시 계산한다