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

---

문제를 구하는 방법은 나와있어 풀기는 쉽지만, 제한 사항에서 정수의 범위가 매우 넓기 때문에, 단순하게 for문을 통해 숙련도를 1씩 증감 하는 방식으로 푼다면 시간제한이 걸린다.

 

이 문제를 해결 하기 위해서는 이진 탐색 알고리즘을 통해 숙련도를 빠르게 찾을 수 있다.

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> diffs, vector<int> times, long long limit) {
    
    long long totalTime=0;
    
    long long start=1;
    long long end=limit;
    
    long long level=(start+end) /2;
    
    
    
    while(start<=end)
    {
        totalTime=0;
        
        for(long long i=0; i<diffs.size();i++)
        {
            if(diffs[i]<=level)
            {
                totalTime+=times[i];
            }
            else
            {
                long long error = diffs[i] - level;
                totalTime +=(times[i]+times[i-1])*error+times[i];
            }
        }
        
        if(totalTime<=limit)
        {
            end = level-1;
        }
        else
        {
            start = level+1;
        }
        
        level = (start+end) /2;
        
    }
    
   
    return level+1;
}

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