프로그래머스 [Level2] 퍼즐게임 ( binary_search 알고리즘)

문제

#include <string>
#include <vector>
#include <set>

using namespace std;

bool calculate_time(int _mid, vector<int> _diffs, vector<int> _times, long long limit)
{
    // 이게 true면 start 땡기기
    
    long long i_TotalTime = 0; 
    
    for(int i=0; i<_times.size(); i++)
    {
        if(_mid >= _diffs[i])
        {
          i_TotalTime += _times[i];    
        }
        
        else
        {
            i_TotalTime += ((_times[i] + _times[i-1]) * (_diffs[i] - _mid) +_times[i]);
            //(time_cur + time_prev) *  (diff-level) + time_cur 
        }
        
        if(i_TotalTime > limit)
            return false; // start 값 = mid + 1  
    }
    
    return true; // end 값 = mid-1; 
}



int solution(vector<int> diffs, vector<int> times, long long limit)
{
    int answer = 0;

    // 조건 1. diff <= level이면  퍼즐을 틀리지않고 time_cur만큼의 시간을 사용해 해결 
    // -> timeCur  만큼 더해주기 
    // 조건 2  diff >  level 이면  diff-level 만큼 틀리고 틀릴 때마다 time_cur 만큼의 시간을 사용하며   
    // 추가로 time_prev 만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야한다. 
    // -> 틀린횟수  :  diff-level 
    // -> 총 total :  (time_cur + time_prev) *  (diff-level) + time_cur 

    // 조건1과 조건2가 limit보다 작게 나오는 것 의 level의 최솟값을 구해라. 

    int startLevel = 1; 
    int endLevel = 100000;
    int mid = 0;  
   
    
    while(startLevel <= endLevel)
    {
        mid = (startLevel + endLevel ) / 2;
        
        if(calculate_time(mid, diffs, times,limit))
        {
            endLevel = mid-1; 
        }
        
        else
        {
            startLevel = mid+1; 
        }
        
    }
    
    answer = startLevel; 
    
    
    
    return answer;
}

 

문제 접근 순서.

 

1. 우선 최솟값의 Level을 구하는 것이므로 Level의 범위부터 생각 ( 1<= Level <= 100,000) 으로 설정

 

2. Level에 따라 결과값이 다르므로 해당 Level을 탐색하기 가장 빠르고 복잡도가 낮은 이진탐색 생각 

 

3. Limit보다 이내에 해야 하니깐  Total_Time < Limit 구조여야 하니깐 이진탐색 조건문이 해제될 때 start 값을 return 해야함

   그래야 Limit보다 작은 값이 나오는 큰 레벨이므로.