1. 문제설명

N개의 집이 수직선 위에 있다.
이 집들 중 일부에 공유기 C개를 설치하고자 한다.
한 집에는 공유기 하나만 설치할 수 있고,
가장 인접한 공유기 사이의 거리를 가능한 크게 설치한다.
C개의 공유기를 N개의 집에 설치해서 공유기 사이 거리의 최대를 구하라.

2. 알고리즘 설계

예를 들어, 1번 부터 6까지의 집, 3개의 공유기가 있다고 해보자.
간격을 1로 공유기를 설치해보자.
- 6개의 공유기를 설치해야 하므로 공유기 개수를 초과한다.
간격을 2로 공유기를 설치해보자.
- 1, 3, 5번 집에 3개의 공유기를 설치할 수 있다.
따라서 예시의 답은 2가 된다.

3. 로직

위에 언급한 조건을 만족하는 거리를 찾는 알고리즘은?
- –> 이분 탐색
left는 어떤 경우든 1이다.
right는 n-1번째의 값과 0번째의 값을 빼주면 된다.
mid 값으로 공유기를 설치하면서 조건을 확인해주면 된다.
- 만약 최초로 조건을 만족했어도, left값을 mid+1해서 탐색해본다.
- 최대값을 찾는 것이기 때문이다.

4. 전체 코드

#include<bits/stdc++.h>
using namespace std;

const int SZ = 200000;
int n, c, arr[SZ];

bool check(int mid) {
	int cnt = 1;
	int prev = arr[0];

	for (int i = 1; i < n; i++) {
		if (arr[i] - prev >= mid) {
			prev = arr[i];
			cnt++;
		}
	}

	if (cnt >= c) return true;
	return false;
}

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

	cin >> n >> c;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	sort(arr, arr + n);

	int result = 0, low = 1, high = arr[n - 1] - arr[0];

	while (low <= high) {
		int mid = (low + high) / 2;

		if (check(mid)) {
			result = max(result, mid);
			low = mid + 1;
		}
		else high = mid - 1;
	}

	cout << result;
	return 0;
}

5. 소감

문제 이해가 너무 오래걸렸다.
예제 1번이 1,2,8,4,9인데 3개의 공유기를 놓았을 때 최대값이 되는 그 값을 구하는 거라고 이해했는데,
뭔가 이상했다.
그래서 알고리즘 단톡방에 문의해보니,
위와 같은 원리를 사용해야 한다는 것이었다.
요즘 문제 티어가 올라가면서, 문제를 이해못하는 상황이 많이 발생하고 있다.

BOJ 2110. 공유기 설치

1. 문제설명

2. 알고리즘 설계

3. 로직

4. 전체 코드

5. 소감