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

🔗링크

1. 문제 풀이

이 문제는 매개 변수 탐색을 통해 풀수 있었다.
매개 변수 탐색(parametric search)이란?

최적화 문제를 결정 문제로 풀 수 있는 기술

최적화 문제 : 가능한 해들 중 가장 최적의 해를 찾는 것
결정 문제 : 답이 이미 결정되었다고 보고 푸는 것

---

쉽게 말하면 특정 범위안에서 조건을 만족하는 해 중
최댓값(Upper Bound) 또는 최솟값(Lower Bound)을
구하는 문제에서 많이 사용된다.

이 문제에서의 해는 C개의 공유기를 설치할수 있는 최대 간격이다.
가능한 간격의 범위는

1 부터 (마지막 집 좌표 - 첫번째 집 좌표)가 되기에.

이 범위 내에서 이분탐색을 활용하여 적절한 간격을 찾아내면 된다.

2. 코드

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;

ll home[200100], N, C, x;

void f() {
	ll left = 1, right = home[N - 1] - home[0], gap, max = 0, cnt, i, cur;
	while (left <= right) {
		gap = (left + right) / 2;
		i = cnt = cur = 0;
		while(i < N&&gap != 0) {
			cnt++;
			while (i < N && home[i] - home[cur] < gap)i++;
			cur = i;
		}
		if (cnt >= C)left = gap + 1;
		else right = gap - 1;
		
	}
	printf("%d\n",right);
}


int main() {
	scanf("%lld %lld", &N, &C);
	for (int i = 0; i < N; i++)scanf("%lld", &home[i]);
	sort(home, home + N);
	f();
	return 0;
}

3. 후기