코딩 테스트 공부 (프로그래머스, 자바)

풀이 아이디어

• DP , Priority Queue
  DP 를 이용해 전에 살펴본 케이스를 갱신할지 안할지 결정
  Priority Queue 를 이용해 소요되는 시간이 적은 케이스 부터 살펴보았다 (정렬 안하면 필요없는 케이스 너무 많음)

모든 문제를 풀 수 있는 수준까지 최소한의 시간을 들여 알고력, 코딩력 을 키우는 것이 문제의 목표이다.

DP 를 이용해 특정 알고력, 코딩력에 도달하는데 걸린 시간을 저장해놓고, 이후에 살펴보는 케이스가 시간이 더 짧았을 경우 DP 를 갱신하고 Queue에 넣어서 더 진행시킨다.
DP 의 크기는 알고력, 코딩력의 최대인 150으로 지정했지만 모든 문제를 푸는데 필요한 최대 알고력(max_alp), 최대 코딩력(max_cop)을 기준으로 Queue 에 넣을지 검사하는 과정으로 처리했다.
(예시. DP[50][50] = 20 --> 20의 시간을 들이면 알고력, 코딩력 50 50 을 키울 수 있다. 이때 새로운 케이스로 알고력, 코딩력 50,50 키우는데 15의 시간을 들이는 것이 들어오면 DP[50][50] = 15 로 갱신)

Priority Queue 를 이용해 소요시간이 적은 케이스부터 살펴봅니다. 이 자료구조를 이용하지 않으면 다음과 같은 불필요한 케이스가 발생할 수 있다.
(예시. 알고력, 코딩력이 50 50 이고 소요 시간이 20인 케이스가 Queue에 들어있는데 알고력, 코딩력 25 25 이고 소요 시간이 14인 케이스가 먼저 들어있으면 이것을 살펴보게 된다.)

import java.util.*;

class Solution {
    static int[][] dp = new int[151][151];
    static int max_alp = 0;
    static int max_cop = 0;
    static int cnt = Integer.MAX_VALUE/2;
    
    public int solution(int alp, int cop, int[][] problems) {
        for(int i = 0; i < problems.length; i++){
            max_alp = Math.max(max_alp, problems[i][0]);
            max_cop = Math.max(max_cop, problems[i][1]);
        }
        
        for(int[] a : dp){
            Arrays.fill(a, Integer.MAX_VALUE/2);
        }
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((int[] a, int[] b) -> {return a[2] - b[2];});
        pq.add(new int[]{alp, cop, 0});
        dp[alp][cop] = 0;
        
        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            if(cnt <= cur[2]) continue;
            for(int i = 0; i < problems.length; i++){
//                 풀 수 있는 문젠지 검사
                if(cur[0] >= problems[i][0] && cur[1] >= problems[i][1]){
                    int[] next = new int[]{cur[0]+problems[i][2], cur[1]+problems[i][3], cur[2]+problems[i][4]};
//                     갱신을 할지 검사
                    if(next[0] >= max_alp && next[1] >= max_cop){
                        dp[max_alp][max_cop] = Math.min(dp[max_alp][max_cop], next[2]);
                        cnt = next[2];
                        continue;
                    }
                    if(next[0] >= max_alp) next[0] = max_alp;
                    if(next[1] >= max_cop) next[1] = max_cop;
                    
                    if(dp[next[0]][next[1]] > next[2]){
                        dp[next[0]][next[1]] = next[2];
                        pq.add(next);
                    }
                }
            }
            // 공부로 1 늘리기
            if(cur[0] < max_alp && dp[cur[0]+1][cur[1]] > cur[2]+1){
                dp[cur[0]+1][cur[1]] = cur[2] + 1;
                pq.add(new int[]{cur[0]+1,cur[1],cur[2]+1});
            }
            if(cur[1] < max_cop && dp[cur[0]][cur[1]+1] > cur[2]+1){
                dp[cur[0]][cur[1]+1] = cur[2]+1;
                pq.add(new int[]{cur[0],cur[1]+1,cur[2]+1});
            }
        }
        return dp[max_alp][max_cop];
    }
}