해결방법

일단, 정렬까진 생각했는데..
이게 어떻게 이분탐색일까 고민해봤다 하지만 해결방법을 못찾음 ^.ㅜ

매개변수탐색

참고 : https://scshim.tistory.com/495
이진탐색(이분탐색)을 사용하여 조건을 만족하는 최대값을 구하는 방법
따라서, 문제 키워드에 "~의 최대값/최소값을 구하시오"가 포함되면 이 방법으로 접근해볼 가치가 있음

1. 정답을 매개변수로 만든다.
2. 문제를 결정문제(Yes or No)로 바꾼다.

문제 해석

결정문제로 만들면?
👉 어떤 거리(d) 만큼 거리를 둘 때, 공유기 C개를 설치할 수 있는가? Yes/No
이 다음은?
거리 d로 공유기 C개 이상 설치 가능 → 거리가 더 커져도 됨 == left = mid+1
거리 d로 공유기 C개까지 설치 안됨 → 거리를 줄여야됨 == right = mid-1

소스코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

int N,C;
vector<int> v;

int main(){
	fastio
	cin>>N>>C;
	for(int i = 0; i<N; i++){
		int x; cin>>x;
		v.push_back(x);
	}
	
	sort(v.begin(),v.end());
	
	//binsearch
	int left = 1; //최소간격 
	int right = v[N-1]; //최대간격 
	int ans = 0;
	while(left<=right){
		int mid = (left + right) / 2;
		int router = 1, start = v[0];
		for(int i = 1; i<N; i++){
			if(v[i]-start>=mid){//거리가 mid 이상이면 공유기 설치 
				router++;
				start = v[i];
			}
		}
		if(router>=C){
			ans = max(ans, mid);
			left = mid + 1;
		}
		else right = mid - 1;	
	}
	
	cout<<ans;
}

제출결과

내가 한 실수 : 변수의 정의를 헷갈림
mid값은 간격임.. 그렇다면 left와 right는 각각 최소간격, 최대간격일텐데
left와 right는 첫 집과 마지막 집의 위치라고 착각하는 바람에 틀렸다