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

 

문제

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

 

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

 

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

 

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

 

 

 

입력

 

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

 

 

출력

 

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

 

 

풀이

 

입력받은 공유기의 위치를 정렬한 다음 공유기 사이의 거리의 기준을 정해 기준을 넘으면 공유기를 설치하고 기준을 넘지 않으면 공유기를 설치하지 않도록 한 다음, 갯수를 세서 목표한 공유기 설치 갯수를 만족하는지 판단했다.

 

거리를 탐색할 때 1부터 가장 멀리 떨어진 공유기까지 하나씩 비교하는 방법은 시간이 오래걸리기 때문에 좌표가 가장 작은 공유기와 가장 큰 공유기의 거리의 절반에 해당하는 위치를 구한 뒤 만약 공유기 갯수를 만족하면 거리를 늘리고 갯수를 만족하지 못하면 거리를 줄였다.(이분탐색)

 

[풀이 핵심]

- 공유기 사이의 최대거리를 이분탐색으로 찾으면서 조건을 만족하는지 비교하는게 핵심이다. 

 

 

 

Code

 

 

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

int N = 0, C = 0;
int* arr;

int find_load(int st, int ed) {
	int mid = (st + ed) / 2; //st와 ed합의 절반을 처음 집 설치 이후 공유기 설치 위치로 정함
	if (st > ed) { // 만약 st가 크다면 목표값을 찾았으므로 stop
		return mid - arr[0];
	}
	int km = mid - arr[0]; // 일정한 이동거리를 구한 값
	int base = arr[0]; // 일정한 이동을 할 집의 위치를 
	int cnt = 1;
	for (int i = 1; i < N; i++) {
		if (arr[i] - base >= km) {
			base = arr[i];
			cnt += 1;
		}
	}
	if (cnt >= C) {
		return find_load(mid + 1, ed);
	}
	else {
		return find_load(st, mid-1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> C;
	arr = new int[N];
	//int idx=0;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N);
	cout << find_load(arr[0],arr[N-1]);
	return 0;
}

 

---

 

 

오랜만에 문제를 다시 보니 새삼 문득 대단 어렵네;

 

2110번: 공유기 설치