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

🏅 Gold 4

✏️ 1차 솔루션

⭐️ 이분 탐색 풀이

1. 집 위치 오름차순 정렬
2. left = 0, right= n - 1
3. mid 인덱스 위치 - left 인덱스 위치 와 right 인덱스 위치 - mid 인덱스 위치 중에 거리가 먼 영역을 이분탐색 영역으로 지정
   ➡️ 만약 오른쪽 영역을 이어서 탐색한다면 left 에 공유기를 세워야하므로 현재 위치와 right 인덱스 위치 거리를 ans 에 저장
4. 현재 mid 에도 공유기를 세우는 것이기 때문에 다음 mid 와 현재 mid 사이 거리를 계산해서 ans 갱신해야하므로 mid 값은 따로 저장해두기

🚨 1차 trouble

그냥 틀려버리는데 맞게 푼건지도 모르겠다..테케는 맞음
시도는 좋았으나 점점 산으로 감,,

✏️ 최종 솔루션

⭐️ 이분 탐색 풀이
⭐️ 모든 공유기간 간격이 x 이상이면서 c 개의 공유기를 세울 수 있을 때 x 값 중에서 최대값을 구해야하는 것
⭐️ 결국 이분 탐색의 범위는 공유기간 거리가 되는 것

1. left = 1, right = 가장 먼 집의 위치
2. 기준점이 필요하기 때문에 첫번째 집은 무조건 공유기 세우고 시작
3. 모든 집을 돌면서 이전 공유기 위치와 현재 집의 거리(x[i]-first>=mid)가 mid 보다 크거나 같으면 현재 집에 공유기를 세우고 공유기 개수 count
   ❗️ mid 가 모든 공유기의 최소 거리가 되는 것
4. 모든 집을 돌면서 세운 공유기 개수가 c 보다 같거나 크면 공유기 간격을 늘려서 공유기를 줄여야하므로 left = mid + 1 로 갱신하고 mid 를 ans 에 갱신
   ❗️ 다음 회차에 공유기 간격을 늘려서 비교했을 때 공유기 개수가 c 보다 작으면 현재 간격이 최대값이 되기 때문에 저장해두기
5. 모든 집을 돌면서 세운 공유기 개수가 c 보다 작으면 공유기 간격을 줄여서 공유기를 늘려야하므로 right = mid - 1 로 갱신

📌 self feedback

이분 탐색의 범위를 인덱스를 기준으로 보지 않고 전체 거리로 봐야 함
공유기 간 간격뿐만 아니라 공유기의 개수도 고려해줘야 했기 때문에 이를 어떻게 처리할지 고민하는 과정이 필요했음

✏️ 최종 code

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

int main() {
    int n,c;
    cin >> n >> c;
    
    vector<int> x(n);
    for(int i=0;i<n;i++) {
        cin >> x[i];
    }
    
    sort(x.begin(),x.end());
    
    int left=1,right=x[n-1],ans=0;
    while (left<=right) {
        int cnt=1;  // 첫번째 집에 1개 설치
        int mid=(left+right)/2;
        int first=x[0]; // 공유기 설치 위치
        for(int i=1;i<x.size();i++) {
            if(x[i]-first>=mid) {
                first=x[i];
                cnt++;  // 공유기 count
            }
        }
        
        if(cnt>=c) {
            ans=mid;
            left=mid+1;
        }
        else {
            right=mid-1;
        }
    
    }
    
    cout << ans << endl;
}