프로그래머스 : 징검다리

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

코딩테스트 연습 - 징검다리

 

​

1~distance 범위 내에서 이분 탐색을 진행하였습니다.

mid를 거리의 최솟값으로 본 뒤, 거리의 최솟값 mid를 유지할 수 있는 상황에서 제거되는 바위의 개수를 이용하여 left의 값을 점차 증가시켜주었습니다.

 

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

int solution(int distance, vector<int> rocks, int n) {
    int l = 1, r = distance;
    sort(rocks.begin(), rocks.end());
    rocks.push_back(distance); // 도착지점과의 거리도 구하기 위함
    while(l <= r) {
        int mid = (l+r)/2; // 거리의 최솟값
        int prev = 0;
        int cnt = 0; // 제거하는 바위의 갯수
        for(int rock : rocks) {
            if(rock - prev <= mid) cnt++; // 제거
            else prev = rock;
        }
        if(cnt <= n) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}