프로그래머스 문제 - 퍼즐 게임 챌린지

프로그래머스 퍼즐 게임 챌린지 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

n개의 퍼즐이 주어집니다.
현재 퍼즐의 난이도를 diff, 현재 퍼즐의 소요 시간을 time_cur, 이전 퍼즐의 소요 시간을 time_prev, 당신의 숙련도를 level이라 생각하여 아래와 같은 조건이 주어집니다.

• diff ≤ level이면 퍼즐을 틀리지 않고 time_cur만큼의 시간을 사용하여 해결합니다.
• diff > level이면, 퍼즐을 총 diff - level번 틀립니다. 퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다. 이전 퍼즐을 다시 풀 때는 이전 퍼즐의 난이도에 상관없이 틀리지 않습니다. diff - level번 틀린 이후에 다시 퍼즐을 풀면 time_cur만큼의 시간을 사용하여 퍼즐을 해결합니다.
  퍼즐 게임에는 전체 제한 시간 limit이 주어지며 난이도, 소요 시간은 모두 양의 정수며, 숙련도도 양의 정수여야 합니다.
  위의 조건에 부합하고 가장 최소가 되는 level의 값을 구해야합니다.

문제 풀이

limit의 제한이 10^15이기 때문에 단순히 계산하는 식으로는 시간초과가 나오게 됩니다.
현재 퍼즐의 난이도가 1 ≤ diffs[i] ≤ 100,000이기에 level이 100000일 경우, 모든 퍼즐을 한번에 해결할 수 있으므로 퍼즐을 푸는 소요 시간을 최대한 적게 사용할 수 있음을 확인할 수 있습니다.
즉, level의 최대값 100000과 최소값 1을 두고 이분탐색을 진행하여 원하는 값을 빠르게 찾아낼 수 있습니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(vector<int> diffs, vector<int> times, long long limit) {
    int answer = 0;
    
    int high = 100000;
    int low = 1;
    int mid;
    long long int totalTime;
    
    while(high >= low)
    {
        mid = (high + low) / 2;
        totalTime = 0;
        for(int i = 0; i < diffs.size(); i++)
        {
            totalTime += times[i];
            if(mid < diffs[i])
            {
                totalTime += (times[i-1] + times[i]) * (diffs[i] - mid);
            }
            
            if(totalTime > limit)
            {
                break;
            }
        }
        
        if(totalTime > limit)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    
    answer = low;
    
    return answer;
}

출저

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