Programmers : 징검다리 건너기

문제링크

풀이요약

파라매트릭 서치

풀이상세

1. mid 값을 뛰어넘은 인원의 수라고 파악하고, 만약 현재 인원만큼 디딤돌의 숫자를 감소시켰을 때 연속으로 $K$ 의 갯수가 나오는 지 확인한다.

2. 모든 인원 가운데 연속으로 $K$ 의 갯수가 나오는 가장 작은 값을 구하는 것이기 때문에 현재 인원이 모두 디딤돌을 지났을 때 $K$ 의 갯수가 나오는 경우면, 최종 답안을 업데이트 한 뒤 $r$ 값을 인원을 줄이고 그렇지 않은 경우는 $l$ 값을 높여 인원을 늘리자

3. 이분탐색이 완료되었을 때 남아있는 최종 답안이 정답이다.

#include <string>
#include <vector>
using namespace std;
int cnt = 0;
bool go(int k, int mid, vector<int> &stones) {
    cnt = 0;
    for(int s : stones) {
        cnt += s-mid<=0 ? 1 : -cnt;
        if(cnt >= k) break;
    }
    return cnt >= k;
}

int solution(vector<int> stones, int k) {
    int l = 1, r = 2e8;
    int mid, ans;
    while(l<=r) {
        mid = (l+r)>>1;
        if(go(k,mid,stones)) {
            ans = mid;
            r = mid -1;
        } else l = mid +1;
    }
    return ans;
}