백준 BOJ 2110 - 공유기 설치

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

2110번: 공유기 설치

처음 보고 뇌절이 심하게 왔었는데,

지문에서

가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

를 보고

저 "가장 인접한 두 공유기 사이의 거리" 가

파라메트릭으로 얻고자 하는 값일거라는 킹리적 갓심을 하고 짜서 AC받았다.

 

가장 인접한 두 공유기 사이의 거리는 아무리 길어도

(오른쪽끝 - 왼쪽끝) 의 길이보다 길 수 없다.

왼쪽끝이 1이라 할때 아무리 커도 오른쪽 끝의 좌표값보단 길 수 없게 되겠다.

일단 파라메트릭을 돌리려면 정렬을 해줘야 하므로 간단히 정렬해줬고 ㅁㄴㅇㄹ

 

#include <bits/stdc++.h>
using namespace std;

int n,c;
int arr[234567] = {0};

int cnt(int k){
	int cnt = 0;
	int prev = 0;
	for(int i=1; i<n; i++){
		if(k <= arr[i]-arr[prev]){
			//printf("[%d] ", i);
			prev = i;
			cnt++;
		}
	}
	return cnt+1;
}

int search(int s, int e){
	int mid = (s+e)/2;
	if(s>e) return mid;
	
	if(cnt(mid) < c) return search(s,mid-1);
	else        return search(mid+1,e);
}

int main(){
	cin >> n >> c;
	for(int i=0; i<n; i++){
		cin >> arr[i];
	}
	
	sort(arr, arr+n);
	//cout << cnt(1);
	cout << search(1,arr[n-1]);
	return 0;
}

cnt함수가 길이가 k로 들어올때 몇개의 공유기를 설치할수있는지 세주는 함수.

공유기가 많이 설치되더라도 결국 언젠가는 최적해로 향할거기때문에 그냥 C보다 큰지안큰지만

판별해줘도 된다.

한번에 깔끔하게 AC.