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

프로그래머스

당신은 순서대로 N개의 퍼즐을 풀어야합니다. 각 퍼즐에는 난이도와 소요 시간이 정해져있습니다. 당신의 레벨이 퍼즐의 난이도보다 크거나 같다면 1회에 해결이 가능하며, 레벨이 낮을 경우 이전 퍼즐과 현재 펴즐을 (난이도-레벨) 만큼 다시 풀어야합니다. 이때 limit 시간 안에 모든 문제를 풀기위해 필요한 최소 숙련도를 구해주세요

 

풀이 방법

이진 탐색 문제입니다. level을 기준으로 탐색하면 됩니다.

int minLevel = 1;
int maxLevel = *max_element(diffs.begin(), diffs.end());

int answer = maxLevel;
    while (minLevel <= maxLevel)
    {
        int curLevel = (minLevel + maxLevel) / 2;
        ... .. 
        ... ..
        ... ..

난이도와 소요 시간은 모두 양의 정수이기 때문에 minLevel을 1로 시작해야합니다.

 

퍼즐을 풀기위해 필요한 시간은 아래와 같습니다

max(diffs[i]-curLevel, 0) * (times[i] + times[i-1]) + times[i];

만약 첫번째 퍼즐이라면 이전 퍼즐의 소요시간을 계산에서 제외해줍니다.

 

계산이 끝난 후 시간이 limit안에 들어간다면 answer을 업데이트해주고,

maxLevel을 curLevel로 바꿔주어 탐색 범위를 조절해줍니다. 

limit보다 많은 시간이 소요된다면 minLevel을 curLevel로 바꾸어 탐색 범위를 조절합니다.

 

정답 코드

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


using namespace std;

int solution(vector<int> diffs, vector<int> times, long long limit) {
    
    int minLevel = 1;
    int maxLevel = *max_element(diffs.begin(), diffs.end());
    
    int answer = maxLevel;
    while (minLevel <= maxLevel)
    {
        int curLevel = (minLevel + maxLevel) / 2;
        
        long long time = 0;
        for (int i = 0; i < times.size(); i++)
        {
            int prev = i == 0 ? 1 : times[i-1];
            time += max(diffs[i]-curLevel, 0) * (times[i] + prev) + times[i];
        }
        
        if (time <= limit)
        {
            maxLevel = curLevel - 1;
            answer = min(answer, curLevel);
        }
        else
            minLevel = curLevel + 1;
    }
    
    return answer;
}