[프로그래머스/C++] 징검다리 건너기

✅ LV.3

📌 2019 카카오 개발자 겨울 인턴십

✏️ 최종 솔루션

⭐️ 이분탐색: 돌의 최대 무게(건널 수 있는 최대 인원)를 기준으로 이분탐색

1. left =0, right = 전체 돌 중 최대 무게
2. mid 계산해서 현재 mid 인원으로 무사히 완주할 수 있는지 검사
   ➡️ mid 보다 돌의 무게가 작을 경우, 그 돌은 건널 수 없기 때문에 모든 돌을 탐색하면서 연속으로 k번 건널 수 없으면 현재 mid 로 완주할 수 없다는 것이므로 false 반환
   ❗️ 연속으로 k번 건널 수 있는지 확인해야하기 때문에 건널 수 있는 돌이 등장하는 순간 cnt 를 0으로 갱신해주는 것이 관건
3. 현재 mid 로 건널 수 있으면 mid 를 늘리기 전에 answer 에 mid 갱신 ➡️ 최대값 탐색시 이때 갱신하는 것은 종특

📌 self feedback

완전탐색으로 풀이했지만,,역시 효율성에서 나락감
이분탐색의 실마리를 찾기가 어려웠음

✏️ 최종 code

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

using namespace std;

bool go(vector<int> &stones,int n,int k) {
    int cnt=0;
    for(int i=0;i<stones.size();i++) {
        if(stones[i]<n) cnt++;
        else cnt=0;
        if(cnt>=k) return false;
    }
    return true;
}

int solution(vector<int> stones, int k) {
    int answer = 0;
    
    int left=0,right=*max_element(stones.begin(),stones.end());
    while(left<=right) {
        int mid=(left+right)/2;
        
        // 현재 mid 로 건널 수 있으면 mid 늘리고 아니면 mid 줄이기
        if(go(stones,mid,k)) {  
            left=mid+1;
            if(answer<mid) answer=mid;
        }
        else right=mid-1;
        
    }
    return answer;
}