[programmers] Lv.3 징검다리 건너기(c++)

이분탐색(링크 추가 예정)

 

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

using namespace std;

bool continuous_0(vector<int>& stones, int mid, int k){    
    int zeros=0;
    for(auto stone: stones){
        if(stone - mid > 0) {
            zeros = 0;
        } else zeros++;
        
        if(zeros >= k) return true;
    }
    return false;
}

int solution(vector<int> stones, int k) {
    int answer = 0;
    int min = 1, max = *max_element(stones.begin(), stones.end());
    
    while(min < max){
        int mid = (max + min)/2;
            
        if(continuous_0(stones, mid, k)) {
            max = mid;
        } else min = mid+1;
    }
    return min;
}

---

문제

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

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

728x90

---

[접근]

하나씩 빼다가 연속된 0이하의 숫자가 k개 이상이면 끝이다.

하나씩 빼는것은 비효율적... 중간값들을 빼주자 -> 이분탐색이었음

k개 이상이면 최소값을 mid값에서 1 증가한 뒤 다시 해주고,

k개 미만이면 최대값을 mid값에서 1 감소시킨 뒤 다시 진행.

만약 최소값이 최대값을 넘어서면 멈추고, min 값이 곧 답!!