퍼즐 게임 챌린지[프로그래머스]

접근법:

left와 right 사이에서의 조건을 만족하는 가장 작은 레벨을 찾기
left와 right 사이의 mid 값에 대하여 퍼즐을 푸는데 걸리는 시간을 계산한다.
제한 시간보다 작거나 같으면 일단 이를 저장하고 더 작은 값으로 테스트 하기위해서 right 를 mid -1 로 줄인다.
반복해서 left가 right 보다 작거나 같을동안만 진행한다.
결과로는 limit 보다 작으면서 가장 작은 level을 리턴한다.

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

int solution(vector<int> diffs, vector<int> times, long long limit) {
    int answer = 0;
    int n = diffs.size();
    int left = 1;
    int right = *max_element(diffs.begin(), diffs.end());
    
    while(left <= right)
    {
        long long mid = (left + right) / 2;
        
        long long time = times[0];
        for(int i = 1; i < n; ++i)
        {
            if(diffs[i] <= mid) time += times[i];
            else if(diffs[i] > mid) time += (times[i] + times[i-1]) * (diffs[i] - mid) + times[i];
        }
        if(time <= limit)
        {
            answer = mid;
            right = mid - 1;
        }
        else 
        {
            left = mid + 1;
        }
        
    }
    return answer;
}

하노이의 탑[프로그래머스]

지게차와 크레인[프로그래머스]