[프로그래머스 4] 징검다리 (C/C++) (★★★)

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int cal(vector<int> rocks, int mid, int distance)
{
    int cnt = 0;
    int prev = 0;
    
    for(int i = 0; i < rocks.size(); i++)
    {
        if(rocks[i] - prev < mid)
        {
            cnt++;
        }
        else
        {
            prev = rocks[i];
        }
    }
    
    // 도착지점과 마지막 돌 체크
    if(distance - prev < mid)
    {
        cnt++;
    }
    
    return cnt;
}
 
int solution(int distance, vector<int> rocks, int n) 
{
    int Max = 0;
    int left = 1;
    int right = distance;
    
    sort(rocks.begin(), rocks.end());
    
    while(left <= right)
    {
        // 바위 사이 거리의 최솟값
        int mid = (left + right) / 2;
        
        if(cal(rocks, mid, distance) > n)
        {
            right = mid-1;
        }
        else
        {
            left = mid+1;
            
            if(mid > Max)
            {
                Max = mid;
            }
        }
    }
    
    return Max;
}