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

 

🧫 문제 분석

✔️ 출처

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

📖 문제

 

이진 탐색 문제다.

 

그런데 이진탐색을 했더니 시간초과나서 다른 방법을 찾아서 삽질을 하고 

식을 제대로 세우고 이진탐색으로 풀었다.

 

문제에서 주어진 조건을 식으로 풀어보면

 아래와 같다. 

limit >= (diff[i] - level) * (time_cur[i] + time_prev[i]) + time_cur[i]

 

이를 만족하는 level 최솟값을 찾으면 된다. 

 

좀만 더 간단히하면

문제에서 diff - level 번 만큼 이전 문제를 다시 풀고(time_prev) + 현재 문제를 다시 풀어야한다(time_cur) 

diff-level 번 틀린 후 다시 풀면 time_cur만큼 시간을 사용한다. 

 

즉, limit - time_cur[i] 를 빼준다. (i = 1~n)

 

(limit - time_cur[i]) >= (diff[i] - level) * (time_cur[i] + time_prev[i])

 

 

 

1 ~ 100,000 사이의 값들을 이진 탐색하면서

위 식에 맞는 최소 숙련도를 찾는다. 

 

 

 

문제를 풀고 난 후 

처음 이진탐색을 떠올리고 바로 해봤는데 시간초과가 났다. (이때는 식을 제대로 세우지 않았던 걸로 기억)

어째서 처음 했을때는 시간초과가 났는지 알 수 없다. 

그 코드를 저장했었다면 더 좋은 학습이 되었을텐데 아쉽다..

그리고 절대절대 소수로 계산하려 하지 말자...

 

 

 

 

---

🔅 2번째 시도

import java.util.*;

class Solution {
    // diff <= level : time_cur만큼 시간 사용
    // diff > level : diff-level 번 틀림, 틀릴때 마다 time_cur만큼 시간 사용 + time_prev 만큼의 시간 사용 (이전 퍼즐 다시 품(이때 절때 틀리지 않음))
    // 난이도, 소요시간, 숙련도 양의 정수
    
    //limit >= (diff[i] - level) * (time_cur[i] + time_prev[i]) + time_cur[i]
    
    // limit / (time_cur[2~n] + time(pre(1~n-1))) >= diff[2~n] - level
    // (diff[2~n] / (n-2)) - limit < level 을 구하고 (level은 ceil() 올림)
    // 이때 level은 diff - level <0 일때를 고려하지 않았다. 즉, 퍼즐을 틀리지 않았을 때도 틀렸다고 가정하고 그만큼 시간을 계산한 것이다.
    // 따라서 한 번 더 level 값을 기준으로 위 식을 다시 계산한다. ㅣ
    // diffs-level <= 0 이면 그 값은 더하지 않는다. 
    
    //
    
    public int solution(int[] diffs, int[] times, long limit) {
        int level = 0;
        int[] timeSum = new int[times.length];
        // 리밋에서 우선 time_cur만큼 뺀다
        limit -= Arrays.stream(times).sum();
        
        
        // time_cur + time_prev
        for (int i = 1; i < diffs.length; i++) {
            timeSum[i] = times[i] + times[i-1];
        }
        
        
        for (int i = 0; i < 2000; i++) {
        // (diff[i] - level) * (time_cur + time_prev)
            long sum = 0;
            int levelMulti = 0;
            for (int j = 1; j < diffs.length; j++) {
                if (diffs[j] > 1 && diffs[j] - level > 0) {
                    sum += (long)diffs[j] * timeSum[j]; 
                    levelMulti += timeSum[j];
                }
            }    
            
            level = (int)Math.ceil((double)(sum - limit) / levelMulti);   

        }
        
        return level;
    }
    
}

기본 테케가 다 풀리고 절반 틀린거같아서 될거같아서 계속 시도하다가 큰 삽질을 하게 되었다.

설명하기도 어렵다. 참 쓰레기 코드다.

 

 

🔅 문제 풀이

import java.util.*;

class Solution {
    // diff <= level : time_cur만큼 시간 사용
    // diff > level : diff-level 번 틀림, 틀릴때 마다 time_cur만큼 시간 사용 + time_prev 만큼의 시간 사용 (이전 퍼즐 다시 품(이때 절때 틀리지 않음))
    // 난이도, 소요시간, 숙련도 양의 정수

    //limit >= (diff[i] - level) * (time_cur[i] + time_prev[i]) + time_cur[i]


    public int solution(int[] diffs, int[] times, long limit) {
        int[] timeSum = new int[times.length];
        
        // 리밋에서 우선 time_cur[i]만큼 뺀다
        limit -= Arrays.stream(times).sum();
        int level = 1;


        // time_cur + time_prev
        for (int i = 1; i < diffs.length; i++) {
            timeSum[i] = times[i] + times[i-1];
        }

        int front = 1, back = 100000;


        while(front <= back) {
            long sum = 0;

            int mid = (front + back) / 2;
            
            // 0번째는 항상 1이기에 넘어감
            for (int j = 1; j < diffs.length; j++) {
            	// diff가 1이 아니고 다시 풀어야하는 문제들만 구한다. 
                if (diffs[j] != 1 && diffs[j] - mid > 0) {
                    sum += (long)(diffs[j] - mid) * timeSum[j];
                }
            }
            
            if (limit >= sum) {
                back = mid - 1;
                level = mid;
            } else {
                front = mid + 1;
            }
        }


        return level;
    }

}

 

❗ 오답노트 / 필요한 지식

1. long타입 안해서 틀리고, 이상한 식 써서 틀리고 ... 참 아직 멀었다.