[Algorithm] Programmers :: 퍼즐 게임 챌린지

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

프로그래머스

 

#include <string>
#include <vector>
#include <math.h>
 
using namespace std;
 
bool check(long long level, vector<int>& diffs, vector<int>& times, long long limit)
{
    long long sum = times[0];
 
    for (int i = 1; i < diffs.size(); ++i)
    {
        int curDiff = diffs[i];
        int curTime = times[i];
        int prevTime = times[i - 1];
 
        if (curDiff <= level)
        {
            sum += curTime;
        }
        else
        {
            int count = curDiff - level;
            sum += count * (curTime + prevTime) + curTime;
        }
    }
 
    if (sum <= limit) return true;
    return false;
}
 
int solution(vector<int> diffs, vector<int> times, long long limit)
{
    int answer = 0;
 
    long long left = 1;
    long long right = pow(10, 15);
 
    while (left <= right)
    {
        long long mid = (left + right) / 2;
 
        if (check(mid, diffs, times, limit))
        {
            right = mid - 1;
            answer = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
 
    return answer;
}

 

무난한 이분탐색 문제.

한가지 주의할점은 초기 left값은 0이 아닌 1로해놔야 한다.

0 하니까 14번테스트케이스에서 틀린다.