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

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

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

using namespace std;

long long getTotalTime(const vector<int> &diffs, const vector<int> &times, int level){
    long long time = times[0];
    
    for(int i=1; i<diffs.size(); i++){
        if(diffs[i] <= level){
            time += times[i];
        }else{
            time += (diffs[i] - level) * (times[i] + times[i-1]) + times[i];
        }
    }
    
    return time;
}

int solution(vector<int> diffs, vector<int> times, long long 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 (getTotalTime(diffs, times, mid) <= limit) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return answer;
}

---

📝 풀이

이 문제 풀이의 핵심은 시간 초과를 하지 않고 최솟값의 숙련도를 탐색하는 법입니다.

숙련도에 따라 총 걸리는 시간은 문제에 주어진대로 코드를 작성하면 됩니다.

현재 퍼즐의 난이도를 diff, 현재 퍼즐의 소요 시간을 time_cur, 이전 퍼즐의 소요 시간을 time_prev, 당신의 숙련도를 level이라 하면, 게임은 다음과 같이 진행됩니다.
diff ≤ level이면 퍼즐을 틀리지 않고 time_cur만큼의 시간을 사용하여 해결합니다.
diff > level이면, 퍼즐을 총 diff - level번 틀립니다. 퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다. 이전 퍼즐을 다시 풀 때는 이전 퍼즐의 난이도에 상관없이 틀리지 않습니다. diff - level번 틀린 이후에 다시 퍼즐을 풀면 time_cur만큼의 시간을 사용하여 퍼즐을 해결합니다.

 

이진 탐색을 하기 위해 left를 1, right를 diffs의 최댓값으로 설정합니다.

mid를 구할 때 (left+right)/2 대신 left + (right - left) / 2를 사용하여 오버플로우가 일어나지 않도록 합니다.

숙련도에 따른 문제 해결 시간을 구한 후 제한 시간보다 작거나 같으면 답을 중앙값으로 갱신하고 right 값을 줄입니다.

제한 시간보다 크다면 left 값을 늘립니다.

최종적으로 answer 값을 return 합니다.