[프로그래머스/Lv.2] PCCP - 퍼즐 게임 챌린지 (Java)

퍼즐 게임 챌린지

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

---

풀이

숙련도(`level`)의 최솟값 + 단조 감소(`level` ↑ -> `total` ↓) => 이분 탐색

 

1 <= diffs[i] <= 100,000

모든 퍼즐의 난이도 >= 최댓값 -> 절대 실패 X

-> 가능한 `level` 범위: 1 <= level <= max(diffs)

=>`lt = 1`, `rt = 100,000`

 

• 실패 X -> 1번만
• 실패 O 
  • 실패 횟수: `diffs[i] - mid`
  • 각 실패마다 `time+cur + time_prev`/ 마지막 성공 시 `time_cur`

if (diffs[i] <= mid) total += times[i];
else {
    int fail = diffs[i] - mid;
    total += times[i] + (long) fail * (times[i] + times[i - 1]);
}

---

코드

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int lt = 1;
        int rt = 100000;
        int ans = rt;
        
        while (lt <= rt) {
            int mid = (lt + rt) / 2;
            long total = 0;
            
            for (int i = 0; i < diffs.length; i++) {
                if (diffs[i] <= mid) total += times[i];
                else {
                    int fail = diffs[i] - mid;
                    total += times[i] + (long) fail * (times[i] + times[i - 1]);
                }
                
                if (total > limit) break;
            }
            
            if (total <= limit) {
                ans = mid;
                rt = mid - 1;
            } else lt = mid + 1;
        }
        
        return ans;
    }
}