[프로그래머스] 코딩 테스트 공부 ⭐

📚 문제 설명

🔎 입출력 예

💻 코드

// 문제를 풀어 알고력, 코딩력을 높인다 (같은 문제 여러 번 가능)
// 모든 문제를 풀 수 있는 알고력과 코딩력을 얻는 최단 시간!
import java.math.*;
class Solution {
    public int solution(int alp, int cop, int[][] problems) {
        int answer = 0;
        int alp_target = 0;
        int cop_target = 0;
        
        // 문제의 가장 높은 alp_req와 cop_req를 각각 알고력과 코딩력으로 가짐
        for(int[] problem : problems) {
            alp_target = Math.max(alp_target, problem[0]);
            cop_target = Math.max(cop_target, problem[1]);
        }
    
        // 초기 알고력과 코딩력이 둘 다 목표치보다 높은 경우 -> 최단시간 0
        if(alp >= alp_target && cop >= cop_target) return 0;
        
        // 초기 알고력이 목표치보다 높은 경우 
        if(alp >= alp_target) alp = alp_target;
        
        // 초기 코딩력이 목표치보다 높은 경우
        if(cop >= cop_target) cop = cop_target;
        
        
        // dp 배열 생성 (정수 최대값으로)
        int[][]dp = new int[alp_target+2][cop_target+2];
        for(int i=alp; i<=alp_target; i++) {
            for(int j=cop; j<=cop_target; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        
        // dp 
        dp[alp][cop] = 0; //시작점
        for(int i=alp; i<=alp_target; i++) {
            for(int j=cop; j<=cop_target; j++) {
                
                // 공부하기
                dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j] + 1);
                dp[i][j+1] = Math.min(dp[i][j+1], dp[i][j] + 1);
                
                for(int p=0; p<problems.length; p++) {
                    // 현재 알고력과 코딩력이 문제를 해결할 수 있는 경우
                    if(i>=problems[p][0] && j>=problems[p][1]) {
                        
                        // 문제를 풀었을때 둘 다 목표치가 넘는 경우
                        if(i+problems[p][2]>alp_target && j+problems[p][3]>cop_target) {
                            dp[alp_target][cop_target] = Math.min(dp[alp_target][cop_target], dp[i][j] + problems[p][4]);                        
                        } // 알고력이 목표치를 넘는 경우
                        else if(i+problems[p][2]>alp_target) {
                            dp[alp_target][j+problems[p][3]] = Math.min(dp[alp_target][j+problems[p][3]], dp[i][j] + problems[p][4]);
                        } // 코딩력이 목표치를 넘는 경우
                        else if(j+problems[p][3]>cop_target) {
                            dp[i+problems[p][2]][cop_target] = Math.min(dp[i+problems[p][2]][cop_target], dp[i][j] + problems[p][4]);
                        } // 둘다 목표치를 넘지 않는 경우 (일반)
                        else {
                            dp[i+problems[p][2]][j+problems[p][3]] = Math.min(dp[i+problems[p][2]][j+problems[p][3]], dp[i][j] + problems[p][4]);
                        }
                    }
                } 
            }
        }
        
        answer = dp[alp_target][cop_target];
        return answer;
    }
}

📖 Solution

최단 시간을 구하는 거니까 bfs로 풀어야할까? 다른 방법으로 풀어야할까? 감이 잘 오지를 않았다...😭
그래서 이 풀이를 참고해서 동적계획법 DP로 풀기로 했다.

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

먼저 동적 계획법은 Top_Down, Bottom_Up 방법으로 나뉜다.

• Top_Down 방법: 큰 문제에서 작은 부분 문제를 재귀적으로 호출하여 리턴 되는 값을 이용하여 큰 문제를 해결하는 방법 (재귀 호출)

• Bottom_Up 방법: 작은 부분 문제들을 미리 계산해두고 이 부분 문제들을 모아 큰 문제를 해결하는 방법 (반복문)

이 문제에서 우리가 알 수 있는 것은 작은 부분이다. 초기 알고력, 코딩력을 알 수 있기 때문에 Bottom_Up 방법을 사용해서 구현했다.

문제를 풀때 선택지는 3가지가 있다.
1. 알고력을 높이기 위한 공부 (+1)
2. 코딩력을 높이기 위한 공부 (+1)
3. 문제 풀기

이 3가지를 DP로 구현하면 된다 🧐

// 1. 알고력을 높이기 위한 공부
dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j] + 1);

// 2. 코딩력을 높이기 위한 공부
dp[i][j+1] = Math.min(dp[i][j+1], dp[i][j] + 1);

// 3. 문제 풀기
dp[i+alp_rwd][j+cop_rwd] = Math.min(dp[i+alp_rwd][j+cop_rwd], dp[i][j] + cost);

하지만 !!! 문제를 풀면서 생기는 변수도 고려해주어야한다 !!!

1. 문제를 풀었을때 목표치를 넘는 경우

for(int p=0; p<problems.length; p++) {
// 현재 알고력과 코딩력이 문제를 해결할 수 있는 경우
   if(i>=problems[p][0] && j>=problems[p][1]) {
                        
     // 문제를 풀었을때 둘 다 목표치가 넘는 경우
     if(i+problems[p][2]>alp_target && j+problems[p][3]>cop_target) {
        dp[alp_target][cop_target] = Math.min(dp[alp_target][cop_target], dp[i][j] + problems[p][4]);                       
     } // 알고력이 목표치를 넘는 경우
     else if(i+problems[p][2]>alp_target) {
        dp[alp_target][j+problems[p][3]] = Math.min(dp[alp_target][j+problems[p][3]], dp[i][j] + problems[p][4]);
     } // 코딩력이 목표치를 넘는 경우
     else if(j+problems[p][3]>cop_target) {
        dp[i+problems[p][2]][cop_target] = Math.min(dp[i+problems[p][2]][cop_target], dp[i][j] + problems[p][4]);
     } // 둘다 목표치를 넘지 않는 경우 (일반)
     else {
        dp[i+problems[p][2]][j+problems[p][3]] = Math.min(dp[i+problems[p][2]][j+problems[p][3]], dp[i][j] + problems[p][4]);
     }
   }
}

2. 초기 알고력과 코딩력이 목표치보다 높은 경우

// 초기 알고력과 코딩력이 둘 다 목표치보다 높은 경우 -> 최단시간 0
if(alp >= alp_target && cop >= cop_target) return 0;
        
// 초기 알고력이 목표치보다 높은 경우 
if(alp >= alp_target) alp = alp_target;
        
// 초기 코딩력이 목표치보다 높은 경우
if(cop >= cop_target) cop = cop_target;

이 변수를 고려하지 않고 풀게 되면 몇개의 런타임 에러들이 발생한다!