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

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

문제

퍼즐 게임에는 전체 제한 시간 limit가 정해져 있습니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구하려고 합니다.

--> 이때, 1 ≤ limit ≤ 10^15 이다.

문제 정의

이 문제는 시간초과를 고려해서 푸는 것이 핵심이다!

처음에는 시간초과이 초과되어 테스트케이스 10~15번에서 돌아가지 않았다.
그리고 시간초과를 어떻게 해결해야될지 몰랐다 ㅠㅠ

[기존 코드]

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

using namespace std;

long long dfs(int level, vector<int> dif, vector<int> tim, long long limt) {
    long long hours = 0;
    for(int i=0; i<dif.size(); i++) {
        if (dif[i] <= level) {
            hours += tim[i];
        } else if (dif[i] > level) {
            if (i>0) {
                hours += (dif[i] - level) * (tim[i]+tim[i-1]) + tim[i];
            } else {
                hours += (dif[i] - level) * (tim[i]) + tim[i];
            }
        }
    }
    return hours;
}

int solution(vector<int> diffs, vector<int> times, long long limit) {
    int answer = 0;
    int level = 1;
    int n = *max_element(diffs.begin(), diffs.end());
    
    for(int i=0; i<n; i++) {
        long long now = dfs(level, diffs, times, limit);
        if (now > limit) {
            level++;
            continue;
        } else {
            return level;
        }
    }
    
    return answer;
}

시간초과를 해결하기 완전탐색 대신, 이진탐색을 해보았다.
그 결과 시간초과가 나지않고 잘 돌아가는 것을 확인할 수 있었다.

[정답 코드]

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

using namespace std;

long long dfs(int level, const vector<int>& dif, const vector<int>& tim) {
    long long hours = 0;
    for(int i=0; i<dif.size(); i++) {
        if (dif[i] <= level) {
            hours += tim[i];
        } else if (dif[i] > level) {
            if (i>0) {
                hours += (dif[i] - level) * (tim[i]+tim[i-1]) + tim[i];
            } else {
                hours += (dif[i] - level) * (tim[i]) + tim[i];
            }
        }
    }
    return hours;
}

int solution(vector<int> diffs, vector<int> times, long long limit) {
    int answer = 0;
    int level = 1;
    int level_max = *max_element(diffs.begin(), diffs.end());
    answer = level_max;  // 최악의 경우
    
    while (level <= level_max) {
        int mid = (level + level_max) / 2; // 이진탐색
        long long now = dfs(mid, diffs, times);

        if (now <= limit) {
            answer = mid;     // 가능한 level
            level_max = mid - 1;  // 더 낮은 level이 되는지 탐색
        } else {
            level = mid + 1;   // 시간 초과 → level 올리기
        }
    }
    
    return answer;
}

단조성

이 문제는 level을 순차적으로 탐색하며 풀이하는 문제이기 때문에 '단조성'의 성질을 활용한다.

단조성은 값이 증가하거나 감소하기만 하는 성질이다.

✔ 단조 증가
1 → 3 → 5 → 9 → 12

항상 커진다.

✔ 단조 감소
100 → 80 → 80 → 50 → 20

작아지기만 한다.(같아지는 것도 OK).

이진 탐색이 단조성을 필요로 하는 이유

이진 탐색은 “왼쪽 절반/오른쪽 절반을 버릴 수 있어야” 의미가 있다.
그런데 그게 가능하려면 정답을 기준으로 양쪽이 반드시 서로 다른 성질을 가져야 한다.

예를 들면:

level ↑ → 걸리는 시간 ↓
(단조 감소)

그래서 mid에서 시간이 limit 이하이면
그 왼쪽으로 가도 되고, 오른쪽은 버릴 수 있다.

즉, 이진 탐색은 단조성이 없으면 못 쓰는 알고리즘이다.

이 문제에서는 level의 최솟값은 1, level의 최댓값은 max(diffs) 이므로 범위가 정해져있고, 단조성을 가지므로 이진탐색을 통해 풀이할 수 있었다.