PCCP 기출문제 2번 / 퍼즐 게임 챌린지

이 문제에서 조심해야 할 점은 데이터 크기이다.

limit이 10^15 이기 때문에 데이터 타입은 long long  타입을 사용해야 한다. (64비트)

 

숙련도의 범위의 최대는 diffs의 최대 값이다.

그 이유는 이 문제의 조건이 limit 이내 가능한 숙련도 레벨을 구하는 것이기 때문에 

숙련도의 레벨이 가장 어려운 난이도라면 모든 퍼즐을 풀 수 있기 때문이다.

 

그렇다면 limit 이내 풀 수 있는 최소 숙련도 값을 구하려면 1부터 diff의 최대 난이도 만큼이 숙련도 레벨의 범위가 된다.

 

이에 대한 각각 하나를 탐색하면서 시간을 계산하면 된다.

 

모든 값을 탐색하면 빅오가 O(n)이므로 이진 탐색을 통해서 O(log n)으로 줄일 것이다.

 

limit 이내라면 숙련도를 낮춰서 탐색

limit 초과라면 숙련도를 높여서 탐색

 

그리고 limit이 초과되면 굳이 더 이상 계산할 필요 없이 return 0으로 종료시킨다.

 

#include <string>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;

// 최적화된 시간 계산 함수
ll calculate_time(const vector<int>& diffs, const vector<int>& times, int level, ll limit) {
    ll total_time = 0;
    for (int i = 0; i < diffs.size(); ++i) {
        int time_cur = times[i];
        if (diffs[i] <= level) {
            total_time += time_cur;
        } else {
            int fails = diffs[i] - level;
            total_time += (ll)fails * (time_cur + times[i - 1]) + time_cur;
        }

        // 누적 시간이 limit을 초과하면 조기 종료
        if (total_time > limit) return total_time;
    }
    return total_time;
}

// 이진 탐색을 통해 최소 숙련도를 찾는 함수
int solution(vector<int> diffs, vector<int> times, ll limit) {
    int left = 1, right = *max_element(diffs.begin(), diffs.end());
    int answer = right;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        ll time_needed = calculate_time(diffs, times, mid, limit);

        if (time_needed <= limit) {
            answer = mid;
            right = mid - 1;  // 더 작은 숙련도로 탐색
        } else {
            left = mid + 1;  // 숙련도를 높여 탐색
        }
    }

    return answer;
}