[C++] 2110: 공유기 설치

골드 Ⅴ

 

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

int C, N;
int houses[200000];

bool isokay(int d) {
	int cnt = 1;
	int cmp = houses[0];

	for (int i = 1; i < N; i++) {
		if (houses[i] - cmp >= d) {
			cnt++;
			if (cnt == C) return true;
			cmp = houses[i];
		}
	}
	if (cnt < C) return false;
}

//"거리" 가 우리가 찾는 값
int main() {
	scanf("%d%d", &N, &C);

	for (int i = 0; i < N; i++) {
		scanf("%d", &houses[i]);
	}

	sort(houses, houses + N);

	int low = 1;
	int high = houses[N - 1] - houses[0];
	int mid;
	int ans = 0;
	while (low <= high) {
		mid = (low + high) / 2;

		//공유기 다 들어간다면
		if (isokay(mid)) {
			printf("d: %d 괜찮음\n", mid);
			low = mid + 1;
			if (ans < mid) ans = mid;
		}
		else {//다 안들어가면 거리 좀 줄여야함
			high = mid - 1;
		}
	}
	printf("%d", ans);
}

 

parametric search

 

그냥 binary search과 parametric search의 다른점

(문제 접근 관점에서)

 

binary search: F F F F T T T T F F F F 

parametric search: T T T T T T F F F F  or F F F F F T T T T T 임 (틀림)

-------> 늘 그런것도 아니네... F F F F F F F F 중에서 가장 T와 가까운 값을 찾는 경우도 될 수 있음 (ex: 방정식 해 찾기)

말 그대로 어떤 상황이든 될 수 있다...

 

형식에서 보면..

binary search는 값을 찾는 경우, upper bound, lower bound 찾는 경우로 나뉘며

얘네들은 그냥 array[mid] < 기준값, array[mid] == 기준값, array[mid] > 기준값 의 대충 세 개로 나뉘지만

 

parametric search는 만족하는경우 / 불만족하는 경우 로 나뉨