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

작성일: 2024-12-12

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/340212

접근 방식

난이도에서 최솟값과 최댓값을 구해서

최솟값부터 하나씩 증가해가면서, 게임이 가능하다면 최솟값을 갱신하면 된다.

잘못된 접근

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = Integer.MAX_VALUE;
        int min = Arrays.stream(diffs).min().getAsInt(); // 최솟값
        int max = Arrays.stream(diffs).max().getAsInt(); // 최댓값
        for(int i=min; i<=max; i++){
            if(game(diffs, times, limit, i)){
                answer = Math.min(answer, i);
            }
        }
        return answer;
    }

    boolean game(int[] diffs, int[] times, long limit, int num){
        long tmp = limit - times[0];
        for(int i=1; i<diffs.length; i++){
            if(diffs[i] <= num){
                tmp -= times[i];
            }else{
                tmp -= (long)(times[i-1]+times[i]) * (diffs[i]-num) + times[i];
            }
            if(tmp < 0L) return false;
        }
        return true;
    }
}

최대 연산 횟수가 30만 * 10만이기에

이분탐색을 통해, 최솟값과 최댓값을 동시에 변경하여 탐색 범위를 최소화해야 한다.

잘 된 접근

while(left<=right){
    int mid = (left + right)/2;
    if(game(diffs, times, limit, mid)){
        answer = Math.min(answer, mid);
        right = mid-1;
    }else{
        left = mid+1;
    }
}

left는 최솟값, right는 최댓값으로 설정하고 중단값을 정한다.

그리고 중단값으로 가능하다면, right을 줄이고, 불가능하다면 left를 올려 값을 구해나간다.

결과

소스 코드

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = Integer.MAX_VALUE;
        int min = Arrays.stream(diffs).min().getAsInt(); // 최솟값
        int max = Arrays.stream(diffs).max().getAsInt(); // 최댓값
        int left=min, right=max;

        while(left<=right){
            int mid = (left + right)/2;
            if(game(diffs, times, limit, mid)){
                answer = Math.min(answer, mid);
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return answer;
    }

    boolean game(int[] diffs, int[] times, long limit, int num){
        long tmp = limit - times[0];
        for(int i=1; i<diffs.length; i++){
            if(diffs[i] <= num){
                tmp -= times[i];
            }else{
                tmp -= (long)(times[i-1]+times[i]) * (diffs[i]-num) + times[i];
            }
            if(tmp < 0L) return false;
        }
        return true;
    }
}