✅ 이분탐색

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43236

풀이

https://mjmjmj98.tistory.com/78

n개의 바위를 빼보며 모든 경우의 수를 따져보기에는 시간초과가 남.
바위 사이의 최소 거리 중 최대 값을 이분탐색으로 가능한지 따져 찾음

이전에 풀었던 [boj] (g4) 2110 공유기 설치 와 흡사한 문제

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool isPossible(int distance, vector<int> rocks, int n, int min_dist){
    
    int prev = 0; // 시작점
    int cnt = 0; // 제거할 바위의 수
    
    for(int i=0;i<rocks.size();i++){
        if(rocks[i] - prev < min_dist){ // 바위 제거
            cnt ++;
        }
        else prev = rocks[i];
    }
    if(distance - prev < min_dist) cnt++;
    
    if(cnt <= n) return true;
    
    return false;
}

int solution(int distance, vector<int> rocks, int n) {
    int answer;
    
    sort(rocks.begin(), rocks.end());
    
    int low = 0, high = distance;
    while(low <= high){
        int mid = (low + high)/2;
        
        if(isPossible(distance, rocks, n, mid)){
            answer = mid;
            low = mid + 1;
        }
        else high = mid - 1;
    }
    
    return answer;
}