[프로그래머스] [C++]징검다리 (binary-search)

1. 문제 

코딩테스트 연습 - 징검다리 | 프로그래머스 (programmers.co.kr)

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

 

2. 결정 문제

이진 탐색을 사용하는 문제

 

보통 dp로 풀 수 있지만  n이 클 때 보통 사용한다.

 

이 문제도 dp로 풀 수 있지만 입력이 엄청 커 이진 탐색을 사용하여 

 

최소의 거리의 최대값을 구하였다.

 

여기서 이진 탐색은 lo 값을 리턴하는데 

 

참인 조건일때 lo를 mid로 설정하기 때문에 lo를 리턴해야한다.

(참인 조건일때 hi를 mid로 설정하면 hi값 리턴)

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
bool isOkay(int dist,  int n, vector<int>& rocks) {
    int carry = 0;
    for(int i = 0; i < rocks.size(); i++) {
        if(rocks[i] + carry < dist) {
            n--;
            carry += rocks[i];
        }
        else
            carry = 0;
    }
    if(n <  0)
        return false;
    return true;
}
 
int bSearch(int distance, int n, vector<int>& rocks) {
    int lo = 0, hi = distance + 1, mid;
    while(lo + 1 < hi) {
        mid = (lo + hi) / 2;
        if(isOkay(mid, n,  rocks))
            lo = mid;
        else
            hi = mid;
    }
    return lo;
}
 
int solution(int distance, vector<int> rocks, int n) {
    int before = 0;
    sort(rocks.begin(), rocks.end());
    rocks.push_back(distance);
    
    for(int i = 0; i < rocks.size(); i++) {
        int tmp = rocks[i];
        rocks[i] = rocks[i] - before;
        before = tmp;
    }
    
    return bSearch(distance, n, rocks);
}