[PCCP 기출문제] 2번 [cpp]

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

알고리즘 : 이진탐색
이유 : 숙련도의 최솟값을 찾는 것. 즉, 제한 시간 내에 퍼즐을 해결할 수 있는 가장 낮은 숙련도를 구하는 것입니다. 이러한 유형의 문제는 특정한 값(여기서는 숙련도)에 대한 최소값 또는 최대값을 찾는 최적화 문제에 해당합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long; // 긴 범위의 정수를 위해 ll로 정의 (long long)

// 주어진 숙련도로 제한 시간 내에 모든 퍼즐을 풀 수 있는지 확인하는 함수
bool canSolveWithLevel(const vector<int>& diffs, const vector<int>& times, int level, ll limit) {
    ll total_time = 0; // 퍼즐을 해결하는데 걸리는 총 시간을 저장
    int n = diffs.size(); // 퍼즐의 개수

    for (int i = 0; i < n; ++i) {
        int diff = diffs[i];      // 현재 퍼즐의 난이도
        int time_cur = times[i];  // 현재 퍼즐을 푸는 데 걸리는 시간

        if (diff <= level) {
            total_time += time_cur;
        } else {
            int retries = diff - level;
            int time_prev = (i > 0) ? times[i - 1] : 0;
            total_time += (ll)retries * (time_cur + time_prev) + time_cur;
        }

        if (total_time > limit) {
            return false;
        }
    }
    return total_time <= limit;
}

// 제한 시간 내에 퍼즐을 모두 해결할 수 있는 최소 숙련도를 찾는 함수
int solution(vector<int> diffs, vector<int> times, ll limit) {
    int left = 1; // 최소 숙련도
    int right = *max_element(diffs.begin(), diffs.end()); // 최대 숙련도
    int answer = right;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (canSolveWithLevel(diffs, times, mid, limit)) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return answer;
}