프로그래머스 - 퍼즐 게임 챌린지

0. 개요

파라메트릭 서치(이분탐색) 문제입니다.

파라메트릭 서치의 경우 아래의 문제풀이 글에서 자세히 설명했으니 참고하시길 바랍니다.

https://ksb-dev.tistory.com/257

프로그래머스 - 디펜스 게임(Java)

 

1. 파라메트릭서치인 이유

파라메트릭서치는 최적의 문제 찾기를 결정 문제로 바꿀 수 있는 알고리즘입니다.

문제에서 "퍼즐을 모두 해결하기 위한 숙련도의 최솟값"을 구하라고 나왔습니다.

이는 최적의 숙련도를 찾으라는 문제입니다.

 

1씩 증가시키며 숙련도를 찾아야할까요?

limit이 10^15인데요?

 

문제의 입출력 예 #1의 정답은 3입니다.

 

숙련도가 3보다 클 때, 문제를 해결할 수 있으며

숙련도가 3보다 작을 때, 문제를 해결할 수 없습니다.

따라서 정답은 3입니다.

 

즉, mid라는 값이 있을 때 

숙련도 값 mid보다 클 때, 문제를 해결할 수 있으며

숙련도 값 mid보다 작을 때, 문제를 해결할 수 없게됩니다.

 

이 mid 값을 이분 탐색을 통해서 결정하는 것입니다.

 

숙련도의 최소 값은 diffs[0]의 값인 1입니다. 이를 left의 시작점으로 두겠습니다.

숙력도의 최대 값은 limit입니다. 이를 right의 시작점으로 두겠습니다.

 long left = 1; // 0번째 인 diffs[0]의 값
 long right = limit;

 

 

left와 right의 중간 값인 mid를 숙련도로 가질 때, 문제에서 주어지는 계산식을 이용해 계산하면 됩니다.

mid의 값이 불가능할 때, mid보다 작은 부분은 어쩌피 불가능하므로 left의 값을 옮깁니다.

mid의 값이 가능할 때, mid보다 큰 부분은 전부 가능하니 right의 값을 옮깁니다.

if(isImPossible(diffs, times, mid, limit)){
    left = mid + 1;
}else{
    right = mid;
}

 

2. 문제 풀이

/*
[문제 풀이]
파라메트릭서치를 이용하면 될듯
이진탐색의 값을 mid라고 하면, level의 값을 mid로 계산
*/
class Solution {
    
    public int solution(int[] diffs, int[] times, long limit) {
        long left = 1; // 0번째 인 diffs[0]의 값
        long right = limit;
        
        while(left < right){
            long mid = (left + right) >> 1;
            
            if(isImPossible(diffs, times, mid, limit)){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        
        return (int) left;
    }
    
    private static boolean isImPossible(int[] diffs, int[] times, long level, long limit){
        long tmp = (long) times[0];
        
        for(int i=1; i<diffs.length; i++){
            if(diffs[i] > level){
                tmp += (diffs[i] - level) * (times[i-1] + times[i]);
            }
            tmp += times[i];
        }
        return limit < tmp;
    }
}