[프로그래머스 2레벨] 퍼즐 게임 챌린지 (C++)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> diffs, vector<int> times, long long limit) {
    int l = 1, r = *max_element(diffs.begin(), diffs.end());
    int answer = 0;
    
    while(l<=r)
    {
        int mid = (l+r)/2; //목표 레벨
        long long total = 0;
        for(int i=0; i<diffs.size(); i++)
        {
            total += times[i]; //기본 퍼즐 풀이 시간
            if(mid < diffs[i]) //diff > level
            {
                int prev_time = (i > 0) ? times[i - 1] : 0; 
                total += (prev_time + times[i]) * (diffs[i] - mid);
            }
        }
        
        if(total > limit) l = mid + 1;
        else 
        {
            r = mid - 1;
            answer = mid;
        }
    }
    return answer;
}

 

목표 레벨에 대해서 이진 탐색을 통해 찾는 문제이다.

먼저 최대값의 경우 level 값 범위 자체가 diffs 값이하 일 수밖에 없으므로, diffs 최대값으로 설정해주었다.

 

이제 주어진 diffs 크기 만큼 퍼즐 풀이 시간 합계를 계산한다.

먼저 diff<=level이든, diff>level 이든 time_cur을 이용해 퍼즐 해결하는 시간은 공통이므로 해당 내용부터 작성한다.

이제 diff>level의 경우에 대해 (이전 시간값 + 현재 시간값) * (현재 난이도 - 현재 레벨) 계산을 통해 추가 시간을 더해준다.

이때 i=0부터 시작하기에 i==0인 경우 예외처리를 해주었다.

 

이렇게 구한 total 시간이 limit보다 크면 레벨의 값을 더 키워야 한다.

따라서 l = mid + 1을 하여 더 큰 값의 범위를 탐색하도록한다.

만약 같거나 작다면, 우리가 원하는 레벨의 값이다.

하지만 더 작은 값을 찾을 수도 있으므로 r = mid - 1을 하여 더 작은 값의 범위를 탐색하며 answer에 현재 레벨을 저장한다.

 

이를 통해 구한 최종 answer이 정답이 된다.