BOJ - 2110 공유기 설치 해결 전략 (C++)

• 문제 링크
  백준 2110번 - 공유기 설치

해결 전략

  본 문제는 전형적인 Binary Search 응용 문제로, 이분 탐색을 요구하는 상황임을 인식하는 것은 어렵지 않다. 다만, 그 구현에 있어서 약간의 센스가 필요한 문제이다. 가장 핵심적인 Tip은 아래와 같은 사실을 인지하는 것이다.

집의 좌표가 아니라, 좌표선 상에서 집 간의 거리를 이용한다.

  그러면 이때, 이분 탐색의 대상은 무엇일까? 그렇다. '인접 공유기 간의 최대 거리'이다. 이 '거리'를 이분 탐색의 대상으로 두면 된다. 즉,

매 탐색에서, "거리 배열에 대해 '현재 기준 거리(mid 값)'를 토대로 공유기를 설치할 때, C 이상의 개수로 설치가 가능한가?"를 판단하면 되는 것이다.

이상으로 설치가 가능할 경우, mid+1 ~ upperBound 구간에 대해 이분 탐색을 더 하고,
이상으로 설치가 불가한 경우, lowerBound ~ mid 구간에 대해 이분 탐색을 더 하면 된다.

  이러한 Idea가 유효한 이유는 다음과 같은 사실 때문이다.

• 첫 번째 집(좌표선 상 최좌측 좌표에 위치한 집)엔 반드시 공유기를 설치한다.
  • 왜냐? 그래야 이득이니까. 우리는 Possibility만 보면 된다.

  이를 위해선, 다음의 구현 팁이 필요할 것이다.

• 우선, 집 좌표들에 대해 정렬해야할 것

• 거리 배열에 대한 '가능 판단' 시, "가장 최근에 공유기를 설치한 집"을 기준으로 거리를 계산할 것

  • 이는 말이 애매해보일 수 있는데, 위의 Idea를 기반으로 직접 구현해보면 이해가 될 것이다.

  문제의 예시를 토대로 시뮬레이션을 돌려보면서 해결하길 바란다.

입력상태 : 1 2 8 4 9
정렬상태 : 1 2 4 8 9
거리배열 :   1 2 4 1

  아래는 정답 코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
// BOJ - 2110 Installing WIFI
using namespace std;

vector<int> house, dist;
int max_dist = 0;

void search_dist(int k, int c, int lo, int hi) {
	int m = (lo + hi) / 2, from_recent = 0, t, inst_cnt = 1;
	if (lo > hi) return;

	for (int i = 0; i < k; i++) {
		t = dist[i] + from_recent;

		if (t >= m) {
			from_recent = 0;
			inst_cnt++;
		}
		else from_recent += dist[i];
	}
	if (inst_cnt >= c) {
		if (m > max_dist)
			max_dist = m;
		search_dist(k, c, m + 1, hi);
	}
	else if (lo != hi) 
		search_dist(k, c, lo, m);
}

int main(void) {
	int n, c, t, t_d;

	cin >> n >> c;
	for (int i = 1; i <= n; i++) 
	{ cin >> t;  house.push_back(t); }

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

	for (int i = 1; i < n; i++) {
		t_d = house[i] - house[i - 1];
		dist.push_back(t_d);
	}
	search_dist(n - 1, c, 1, 1000000000);
	cout << max_dist;

	return 0;
}