[프로그래머스] 징검다리

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

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool binarySearch(int& n, vector<int>& stones, int& k) { //못건넌다!!!
    int cnt = 0;
    for (int i = 0; i < stones.size(); i++) {
        if (stones[i] - n <= 0) cnt++;
        else cnt = 0;
        if (cnt >= k)return true;
    }
    return false;
}

int solution(vector<int> stones, int k) {
    int answer = 0;
    int Start = 1; int End = *max_element(stones.begin(), stones.end());
    while (Start <= End) {
        int mid = (Start + End) / 2;
        if (binarySearch(mid, stones, k)) End = mid - 1; //못건너면 사람 줄여서 줄인 사람은 건널 수 있는지 알아본다.
        else Start = mid + 1; //건너면 사람 늘려서 더 건널 수 있는지 알아본다.
    }
    return Start;
}

하나씩 빼가면서 체크 하는 형식으로 풀었으나 제한 사항이 200,000,000으로 인한
시간 초과가 걸렸다. 찾아보니 이분탐색으로 푸는게 답이였다.

#include <string>
#include <vector>

using namespace std;

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