[Programmers/C++] 퍼즐 게임 챌린지

시간 복잡도

• n이 최대 300,000이기 때문에 $O(N^2)$인 알고리즘은 사용할 수 없습니다.

문제 접근법

• 숙련도를 기준으로 이분탐색을 진행합니다.
• 이 때 l=1, r은 퍼즐 문제를 푸는데 걸리는 시간의 최댓값으로 초기화 합니다.
• 퍼즐 문제를 푸는데 걸린 시간의 총 합이 제한 시간보다 작거나 같다면 숙련도를 낮추고
• 그렇지 않으면 숙련도를 높힙니다.

코드

// Programmers
// Level2 퍼즐 게임 체인지

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> diffs, vector<int> times, long long limit) {
    int answer = 0;
    
    int l=1;
    int r=0;
    int mid=0;
    for(int i : diffs)
        r=max(r, i);
    
    while(l<=r)
    {
        long long solveTime=0;
        mid = (l+r)/2;
        
        for(int i=0; i<diffs.size(); i++)
        {
            int count = diffs[i]-mid;
            if(count > 0)
                solveTime+=(times[i]+times[i-1])*count + times[i];
            else
                solveTime+=times[i];
        }

        if(solveTime<=limit)
            r=mid-1;
        else
            l=mid+1;
    }
    answer = l;
    
    return answer;
}