[BOJ] 2110. 공유기 설치 (binary_search, parametric_search)

Gold IV

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

2110번: 공유기 설치

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

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

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

 

input:

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

output:

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

 

 

---

Idea :

• 처음에는 dfs를 생각했지만.. N값을 보면 당연히 시간초과가 나올 수 밖에 없다..!
• 결국 hint와 다른 코드를 참고해서 binary search이고 기준이 공유기 사이 거리임을 알 수 있었음

 

• binary search
  • 찾고자 하는 값 = C개 이상 설치했을 때의 공유기 사이 거리 최댓값 → 기준 = 공유기 사이 거리
  • init - start = 거리 최솟값 = 1, end = 거리 최댓값 = 마지막 집 위치 - 첫 번째 집 위치
  • start와 end의 중간값 mid를 공유기 사이 거리로 했을 때
    • C개 이상 설치가 가능하면,
      공유기 사이 거리 최댓값을 찾기 위해 (mid + 1 ~ end) 로 binary search 반복
    • C개 이상 설치가 불가능하면,
      C개 이상 설치가 가능한 거리를 구해야 하므로 (start ~ mid -1) 로 binary search 반복

Code :   

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

using namespace std;

int N, C;
vector<int> houses;
int answer = 0;

/* checker: 공유기 사이 거리기 dist로 했을 때 설치할 수 있는 개수를 구하고
 *          설치해야 하는 개수 조건 C를 충족하는지 확인하는 함수
 * 
 * parameter - dist: 공유기 사이 거리 
 * return - dist를 사이 거리로 공유기를 설치했을 때 설치 가능한 개수가 C 이상이면 true, C 미민이면 false
 */
bool checker(int dist) {
	vector<int>::iterator prev = houses.begin();
	int wifi_cnt = 1; // 설치한 공유기 개수 
	for (auto cur = houses.begin()+1; cur < houses.end(); cur++) {
		if (*cur - *prev < dist) continue; 
		
		// prev 집과 cur 집 사이 거리가 dist 이상일 경우
		wifi_cnt++;
		prev = cur;

		// 공유기 설치 개수 >= C
		if (wifi_cnt >= C) return true; 
	}
	// 공유기 설치 개수 < C
	return false;

}

/* binary_search: 이분 탐색으로 가장 인접한 두 공유기 사이 거리의 최댓값을 구하는 함수
 *
 * parameters - min_dist: 공유기 사이 거리 최솟값
 *            - max_dist: 공유기 사이 거리 최댓값
 * no return
 */
void binary_search(int min_dist, int max_dist) {
	if (min_dist > max_dist) return; // wrong range

	int mid = (min_dist + max_dist) / 2;

	// mid가 공유기 사이 거리일 때, C개 설치를 할 수 없으므로 거리를 더 줄여야 됨
	if (!checker(mid)) 
		binary_search(min_dist, mid-1);
		
	// mid가 공유기 사이 거리일 때, C개 이상 설치할 수 있으므로 거리를 더 늘려야 됨 
	else {
		answer = max(answer, mid);
		binary_search(mid+1, max_dist);
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// freopen("input.txt", "rt", stdin);

	cin >> N >> C;
	for (int i=0; i<N; i++) {
		houses.push_back(0);
		cin >> houses[i];
	}

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

	binary_search(1, houses[N-1] - houses[0]);

	cout << answer << "\n";
}

 

---

Result : 

메모리: 3688 KB,  시간: 32 ms

 

Review :