[C++] 프로그래머스 2019 카카오 개발자 겨울 인턴십 - 징검다리 건너기

(2시간) 정확성은 쉬운데 도저히 효율성 올릴 아이디어가 안떠올라서 다른 사람 풀이를 참고했다. ㅋㅋ 이분탐색 쓸 생각조차 못했다...

 

정확성만 맞은 방법(1부터 순서대로 카운팅)

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    bool check = true;
    while(check){
        int step = 0;
        for(int i=0; i<stones.size(); i++){
            if(stones[i] != 0){
                stones[i]--;
                step = 0;
            }else{
                step++;
                if(step == k){
                    check = false;
                    break;
                }
            }
        }
        
        if(check){
            answer++;
        }
    }
     
    return answer;
}

 

정확성 효율성(1부터 200000000까지 범위에서 이분탐색)

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

using namespace std;

bool crossStones(int num, int k, vector<int> stones){
    int step = 0;
    for(int i=0; i<stones.size(); i++){
        if(stones[i] - num > 0){
            step = 0;
        }else{
            step++;
            if(step == k) return false;
        }
    }
    return true;
}

int solution(vector<int> stones, int k) {
    int left = 1;
    int right = 200000000;
    while(left <= right){
        int mid = (left + right) / 2;
        if(crossStones(mid, k, stones)){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }

    return left;
}