[알고리즘/문제풀이][BOJ 2110번] 공유기 설치

공유기 설치는 최적의 값을 찾는 문제를 참과 거짓을 결정하는 문제로 변환하여 이분법을 통해 해결할 수 있는 문제입니다.

문제의 지문을 그대로 해석하면 가장 인접한 공유기의 거리의 최대값을 구하는 문제로 생각할 수 있습니다. 이러한 최적화 문제를 참과 거짓을 결정하는 결정 문제로 변환하여 이분법을 이용하여 쉽게 해결할 수 있습니다.

위의 최적화 문제를 다음과 같은 결정 문제로 변환할 수 있습니다.

"가장 인접한 공유기의 거리가 x이상이 되도록 공유기를 설치할 수 있을까" 

이 질문에 대해서는 참 또는 거짓으로만 답을 할 수 있습니다. 만약 이 질문의 답이 참이라고 가정하면 가장 인접한 공유기의 거리가 x 이하인 모든 값으로 설치가 가능하다는 자명한 사실을 알 수 있습니다.  따라서 x이하의 값에 대해서는 더 이상 계산을 할 필요가 없어집니다. 이러한 방식으로 탐색 범위를 좁혀나가면서 최종적으로 참이 되는 최대의 x 값을 구할 수 있게 됩니다. 방식은 이분법과 동일합니다.

위의 질문의 풀이 방법은 탐욕법을 사용하면 간단히 해결할 수 있습니다.

작성한 코드는 다음과 같습니다.

#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable : 4996)
//https://ark-tistory.com

int N;
int C;
int house[200020];

int compare(const void* a, const void* b) {
	if (*(int*)a > *(int*)b) return 1;
	else return -1;
}

void input() {
	scanf("%d", &N);
	scanf("%d", &C);
	for (int i = 0; i < N; i++) {
		scanf("%d", &house[i]);
	}
	qsort(house,N,sizeof(int),compare);
}

int is_ok(int dis) {
	int limit = -1;
	int cnt = 0;
	for (int i = 0;i<N; i++) {
		if (limit <= house[i]) {
			cnt++;
			limit = house[i] + dis;
		}
	}

	if (cnt >= C) return 1;
	else return 0;
}

int main(void) {

	input();

	int ans = 0;
	int lo = 0;
	int hi = house[N - 1] - house[0];
	while (lo <= hi) {
		int mid = (lo + hi) / 2;

		if (is_ok(mid) == 1) {
			ans = mid;
			lo = mid + 1;
		}
		else {
			hi = mid - 1;
		}
	}

	printf("%d\n", ans);
}

문제는 다음의 링크에서 확인할 수 있습니다.

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