[프로그래머스/C++][PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

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

 

문제 분석

해당 문제는 제한된 시간 내에 퍼즐 게임을 해결할 수 있는 숙련도의 최소값 을 찾는 문제입니다.

규칙은 다음과 같습니다.

• 퍼즐 난이도 diff가 숙련도 level보다 작거나 같으면, 시간 time_cur만 사용하여 해결합니다.
• 퍼즐 난이도 diff가 숙련도 level보다 크면, 틀린 만큼(= diff - level)의 추가 시간을 사용하게 됩니다. 이때 매번 틀릴 때마다 현재 퍼즐을 다시 풀고 이전 퍼즐도 다시 풀어야 합니다.
• 제한 시간 내에 모든 퍼즐을 풀 수 있어야 합니다.

이 문제를 풀기 위해 숙련도를 매개변수로 사용하는 이진탐색을 활용했습니다.

 

알고리즘

• 숙련도 범위 설정: 숙련도는 최소 1에서 최대 100,000까지 가질 수 있습니다.
• 이진 탐색: 중간값을 구하고 해당 숙련도에서 퍼즐을 풀 수 있는지 여부를 확인합니다.
• 가능한지 확인 (possible 함수): 주어진 숙련도로 퍼즐을 풀 수 있는지 계산합니다. 현재 숙련도가 각 퍼즐 난이도보다 크거나 같으면 해당 퍼즐을 정상적으로 풀 수 있지만, 그렇지 않으면 틀리는 횟수만큼의 추가 시간이 발생합니다. 이 과정을 모든 퍼즐에 대해 반복하면서 총 소요 시간이 제한 시간을 넘는지 체크합니다.
• 결과 저장: 이진 탐색을 진행하며 조건을 만족하는 최소 숙련도를 찾습니다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
 * n 개의 퍼즐을 제한 시간 내에 풀어야 한다
 * 각 퍼즐은 난이도와 소요시간이 정해져 있다
 * 숙련도에 따라 퍼즐을 풀 때 틀리는 횟수가 바뀐다
 *
 * diff <= level : time_cur 만큼
 * diff > level : diff - level 만큼 틀리고, 틀릴때 마다 time_cur 만큼을 추가로 소모
 *                  + 이전 퍼즐을 모두 풀고 와야 한다 (이때는 틀리지 않음)
 * 이전 퍼즐을 다시 풀 때는 난이도에 상관 없이 틀리지 않음
 *
 */

bool possible(int level, vector<int>& diffs, vector<int>& times, ll limit){

    ll current_time = 0;
    ll prev_time = 0;

    for(int i = 0; i<diffs.size(); i++){
        if(level >= diffs[i]){
            current_time += times[i];
        }else{
            ll repeat = diffs[i] - level;
            current_time += times[i] + (times[i] + prev_time) * repeat;
        }
        prev_time = times[i];
        if(current_time > limit) return false;
    }
    return true;
}

int solution(vector<int> diffs, vector<int> times, long long limit) {

    int l = 1;
    int r = 200000;
    int ans = INT_MAX;

    while (l <= r){
        int mid = (l + r)/2;
        if(possible(mid, diffs, times, limit)){
            r = mid - 1;
            ans = min(mid, ans);
        }else{
            l = mid + 1;
        }

    }
    return ans;
}