[ 프로그래머스 PCCP 기출문제 2번 ] 퍼즐 게임 챌린지 (C++) - 이분 탐색

---

🔗 문제 링크

프로그래머스

 

---

💡 문제 풀이 및 해석

1. 숙련도를 구해야 하는데, 난이도와 시간의 배열이 상당히 크다.
2. 숙련도가 어느 정도일지 예상이 안가고, 예제를 보니 1,2,3, ... 이런식으로 가면 최악의 시간 만족도를 충족시킬 수 없다.
3. 여기서는 하나씩 체크하는 방식이 아닌 범위를 잡고 좁혀들어가는 이분 탐색 방식이 어울리는 것을 알 수 있다.
4. 숙련도와 level에 대해서는 문제에서 설명한 방식 그대로 구현한 것이여서 생략하겠습니다.

---

⭐️ 정답 코드 및 설명

#include <string>
#include <vector>

using namespace std;

bool puzzle(vector<int> diffs, vector<int> times, long long limit, int level) {
    long answer = 0;

    if (diffs[0] > level) answer += (diffs[0] - level + 1) * times[0];
    else answer += times[0];

    for (int i = 1; i < diffs.size(); i++) {
        int diff = diffs[i], time = times[i], time_prev = times[i - 1];
        if (diff > level) answer += (diff - level) * (time_prev + time) + time;
        else answer += time;
    }

    return answer > limit;
}

int solution(vector<int> diffs, vector<int> times, long long limit) {
    int answer = 0;

    int left = 0, right = 9876543210;

    while (left + 1 < right) {
        int mid = (left + right) / 2;
        if (puzzle(diffs, times, limit, mid)) left = mid;
        else right = mid;
    }

    return right;
}

---

🤔 문제 후기

문제는 되게 쉽게 풀었는데, if (diff > level) answer += (diff - level) * (time_prev + time) + time; 이 부분에서 i == 0을 예외처리하고 조건을 복붙해서 (time_prev + time)을 넣어주지 않아서 이거 찾는데 30분이 걸렸다. 막히는게 있다면 가끔 쉬운 부분에서 막히는게 아닐까 다시한 번 생각해보면 좋을 것 같은 문제였다.