[pro] 프로그래머스 level3 118668 코딩 테스트 공부 (Java) - dp

[문제]

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

프로그래머스

 

[풀이]

dp 문제이다.

dp[i][j] = k, 알고력 i와 코딩력 j 에 도달하기 위한 최단 시간 k를 저장한다. (최단시간을 갱신하기 위해 초기값은 max value로 설정한다.)

 

알고력과 코딩력을 올릴 수 있는 방법은 다음 3가지가 존재하며 점화식은 다음과 같다.

 

1. 알고리즘 공부. 알고력을 1 올리기 위해 시간이 1 소요됨.

dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j]+1)

 

2. 코딩 공부. 코딩력을 1 올리기 위해 시간이 1 소요됨.

dp[i][j+1] = Math.min(dp[i][j+1], dp[i][j]+1)

 

3. 문제를 풀어서 알고력과 코딩력을 올릴 수 있음. 시간이 cost 만큼 소요됨. 

dp[i+rwd_a][j+rwd_c] = Math.min(dp[i+rwd_a][j+rwd_c], dp[i][j]+cost)

이때 주의할 점은 현재의 알고력과 코딩력 i, j가 문제를 풀기 위해 요구되는 req_a, req_c보다 작으면 해당 문제를 풀 수 없다. 또한 i+rwd_a 또는 j+rwd_c가 목표치인 goal_a, goal_c를 초과하는 경우에 대해 goal_a, goal_c로 보정해주어야 런타임 오류가 발생하지 않는다.

 

추가로 초기의 알고력과 코딩력이 모두 목표치를 넘어설 경우 0을 반환하며, 하나만 넘어서는 경우 오류를 막기 위해 goal_a, goal_c로 보정해준다. 

 

https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/

2022 테크 여름인턴십 코딩테스트 해설

 

[코드]

 

class Solution {
    public int solution(int alp, int cop, int[][] problems) {
           
        int goal_a = 0;
        int goal_c = 0;
        //목표치를 구하는 for문
        for(int i=0; i<problems.length; i++){
            goal_a = Math.max(problems[i][0], goal_a);
            goal_c = Math.max(problems[i][1], goal_c);
        }
        
        //초기값이 목표치보다 큰 경우
        if(goal_a <= alp && goal_c <= cop){
            return 0;
        }
        
        //하나만 큰 경우 목표치로 보정. dp[goal_a][goal_c]를 구해야하기 때문에
        if(alp >= goal_a){
            alp = goal_a;
        }
        if(cop >= goal_c){
            cop = goal_c;
        }
        
        int[][] dp = new int[goal_a+2][goal_c+2];
        
        //dp 초기화
        for(int i=alp; i<=goal_a; i++){
            for(int j=cop; j<=goal_c; j++){
                dp[i][j]=Integer.MAX_VALUE;
          }
        }
        
        dp[alp][cop]=0;
        
        for(int i=alp; i<=goal_a; i++){
            for(int j=cop; j<=goal_c; j++){  
                
                //1.알고리즘 공부로 알고력을 1 증가시키는 경우 
                dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j]+1);
                
                //2.코딩 공부로 코딩력을 1 증가시키는 경우
                dp[i][j+1] = Math.min(dp[i][j+1], dp[i][j]+1);
                
                //3. 문제를 풀어서 알고력과 코딩력을 증가시키는 경우
                for(int[] p : problems){
                    int req_a = p[0];
                    int req_c = p[1];
                    int rwd_a = p[2];
                    int rwd_c = p[3];
                    int cost = p[4];
                    
                    if(req_a > i || req_c > j) continue;
                    
                    //목표치를 초과하는 경우 보정
                    //1) 둘 다 넘는 경우
                    if(i+rwd_a > goal_a && j+rwd_c > goal_c){
                        dp[goal_a][goal_c] = Math.min(dp[goal_a][goal_c], dp[i][j]+cost); 
                    }
                    else if(i+rwd_a > goal_a){
                        dp[goal_a][j+rwd_c] = Math.min(dp[goal_a][j+rwd_c], dp[i][j]+cost); 
                    }
                    else if(j+rwd_c > goal_c){
                        dp[i+rwd_a][goal_c] = Math.min(dp[i+rwd_a][goal_c], dp[i][j]+cost); 
                    }
                    else{
                        dp[i+rwd_a][j+rwd_c] = Math.min(dp[i+rwd_a][j+rwd_c], dp[i][j]+cost); 
                    }
     
                }
            }
        }
        return dp[goal_a][goal_c];
    }
    
 
}