백준 2110번. 공유기 설치

백준 2110번. 공유기 설치

1. 문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

2. 입력

• 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다.
• 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

3. 출력

• 첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

4. 풀이

아직 완벽하게 이해는 못 했다.

• 간격으로 줄 수 있는 값 중 최댓값을 찾으면 된다.
• 최댓값 찾는 과정을 이진 탐색으로 하면 된다.
• 떡볶이 떡 길이 찾는 문제와 유사하다.
• 나중에 다시 한 번 풀어야겠다.

4-1. 풀이

💡 21.08.06 추가

• 집 순서가 뒤죽 박죽이라서 정렬을 먼저 해준다.
• 집 사이의 거리를 이진 탐색 해주어야 한다.
• start를 1로 설정한다.
• end를 처음 집에서 가장 먼 집까지의 거리로 한다.
• value에 처음 집 인덱스를 대입한다.
• value + mid 값이 house[i] 값보다 작으면 공유기를 설치한다.
  value: 현재 위치, mid: 공유기 설치 거리
• 공유기 설치 개수가 최소 개수보다 적다면 거리를 줄여서 더 많은 공유기를 설치해야한다.
• 공유기 설치 개수가 필요한 공유기 수를 만족한다면 해당 값을 저장하고 거리를 늘려서 탐색한다.
  이 과정에서 최대거리를 갱신한다.

5. 처음 코드와 달라진 점

• 사실 그 전에도 몇 번 시도했다가 실패한 문제였고
• 이해가 잘 안 가서 도움을 받았다.

6. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> houses;

int main() {
	int n, c;
	cin >> n >> c;

	for (int i = 0; i < n; i++) {
		int house;
		cin >> house;
		houses.push_back(house);
	}

	sort(houses.begin(), houses.end());

	int start = 1;
  int end = houses[n - 1] - houses[0];
  int result = 0;

	while (start <= end) {
		int mid = (end + start) / 2;
    int cnt = 1;
		int value = houses[0];

		for (int i = 0; i < n; i++) {
			if (value + mid <= houses[i]) {
				value = houses[i];
				cnt++;
			}
		}

		if (cnt >= c) {
			result = mid;
			start = mid + 1;
		}
		else end = mid - 1;
	}
	cout << result << endl;
}