퍼즐 게임 챌린지

문제 링크

문제 풀이 시간 :

문제 요약

• 퍼즐을 순서대로 풀며, 숙련도 level이 난이도 diff보다 낮으면 diff - level번 틀린다
• 한 번 틀릴 때마다 현재 퍼즐 시간 time_cur과 이전 퍼즐 시간 time_prev를 합쳐서 소비한다
• 모든 퍼즐을 limit 시간 안에 풀 수 있는 최소 level을 구해야 한다
• diffs[0]은 항상 1로 주어져서 첫 퍼즐은 절대 틀리지 않는다

문제 풀이

처음에는 숙련도를 1부터 하나씩 올려가면서, 각 숙련도마다 전체 소요 시간을 시뮬레이션해 처음으로 limit 이하가 되는 값을 찾으면 되겠다고 생각했다.

하지만 이 방식은 비효율적이다.

diff는 최대 100,000까지 나올 수 있어서 시도해야 할 숙련도 후보가 최대 10만 개다.

한 번의 시뮬레이션도 n(최대 300,000)에 비례하는 시간이 걸리므로, 전부 시도하면 100,000 × 300,000번의 연산이 필요해 시간 안에 끝날 수 없다.

이 문제의 핵심은 숙련도가 오를수록 전체 소요 시간은 절대 늘어나지 않는다는 점이다.

숙련도가 높아지면 틀리는 횟수(diff - level)가 줄어들거나 그대로이기 때문에, 전체 시간은 숙련도에 대해 단조 감소한다.

그래서 숙련도를 하나씩 확인하는 대신, right를 diffs 중 최댓값으로 두고 이분 탐색으로 조건을 만족하는 최소 숙련도를 찾을 수 있다.

mid 값 하나를 정하면 처음부터 끝까지 훑으면서 전체 시간을 구하고, 그 값이 limit 이하면 더 낮은 숙련도도 가능한지 왼쪽 구간을 보고, 초과하면 오른쪽 구간을 본다.

이때 중요한 점은, diffs[0]이 항상 1로 주어지기 때문에 첫 번째 퍼즐은 숙련도가 아무리 낮아도 틀리지 않는다는 것이다.

그래서 시뮬레이션에서 times[0]은 조건 없이 그대로 더하고, 두 번째 퍼즐부터만 diff와 mid를 비교한다.

틀렸을 때 추가되는 시간은 (이전 퍼즐 시간 + 현재 퍼즐 시간) × 틀린 횟수이고, 여기에 마지막으로 정답을 맞히는 한 번의 times[i]를 더해준다.

이분 탐색이 끝나면 left가 조건을 만족하는 최소 숙련도가 된다.

최종 코드

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        int right = 0;
        int left = 1;
        int n = diffs.length;
        
        for(int i=0;i<n;i++){
            right = Math.max(right, diffs[i]);
        }
        
        while(left<=right){
            int mid = (left + right)/2;
            
            long time = times[0];
            
            for(int i=1;i<n;i++){
                if(diffs[i] <= mid){
                    time+=times[i];
                    continue;
                }
                
                time+=(long)(times[i-1]+times[i]) * (diffs[i] - mid);
                time+=times[i];
            }
            
            
            if(time <= limit)
                right = mid - 1;
            else
                left = mid + 1;
        }
        
        return left;
    }
}