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

문제 풀이 방법

당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.
초기의 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요.

 

문제에서 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하라고 합니다.

알고력을 높이기 위해 알고리즘 공부를 합니다. 알고력 1을 높이기 위해서 1의 시간이 필요합니다.코딩력을 높이기 위해 코딩 공부를 합니다. 코딩력 1을 높이기 위해서 1의 시간이 필요합니다.현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높입니다. 각 문제마다 문제를 풀면 올라가는 알고력과 코딩력이 정해져 있습니다.

 

알고력 1을 높이기 위해선 1시간이 필요하고,

코딩력 1을 높이기 위해선 1시간이 필요하고,

문제를 풀면 알고력과 코딩력이 올라갑니다.

 

최대한 문제를 풀 수 있는 알고력과 코딩력을 기르고, 문제를 풀어서 획득한 알고력과 코딩력으로 다른 문제를 바로 푸는 것이 제일 베스트 입니다. 따로 알고력과 코딩력을 높이기 위해서 시간을 들이지 않아도 되기 때문입니다.

 

고려해야할 점이 무엇일까요?

 

행동의 갯수가 크게 3가지가 존재합니다.

알고력을 높이기, 코딩력 높이기, 문제 풀기

 

문제를 풀땐, 풀 수 있는 문제의 순서가 정해진 것이 아닌, 풀고 싶은 문제를 풀 수 있다는 점입니다.

예를 들어, 문제가 A,B,C 이렇게 3개가 존재하는 경우에는 A문제→B문제→C문제 순으로 풀어도 되고, B문제→C문제→A문제 순으로 풀어도 됩니다.

 

문제를 다 풀 수 있다는 것은 곧 주어진 모든 문제의 최대 알고력과 최대 코딩력을 만족시켜야 함을 의미합니다.

최대 알고력과 최대 코딩력을 빨리 달성하는 것이 곧 주어진 문제를 모두 푸는 것을 의미합니다.

 

DP를 사용해서 해당 알고력과 해당 코딩력을 도달하는데 필요한 최단 시간을 갱신하면서, 최대 알고력과 최대 코딩력이 도달할때까지 진행합니다.

 

풀이 코드

import java.util.*;

class Solution {
    
    private int[][] dp;
    
    private static int answer = Integer.MAX_VALUE;
    
    public int solution(int alp, int cop, int[][] problems) {
        int answer = 0;
        
        int max_alp = 0;
        int max_cop = 0;
        
        for(int[] problem: problems) {
            max_alp = Math.max(max_alp, problem[0]);
            max_cop = Math.max(max_cop, problem[1]);
        }

        alp = Math.min(alp, max_alp);
        cop = Math.min(cop, max_cop);
        
        dp = new int[max_alp + 1][max_cop + 1];
        
        for(int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        
        dp[alp][cop] = 0;
        
        // 그냥 알고, 코딩력을 올리는 경우
        for(int a = alp; a <= max_alp; a++) {
            for(int c = cop; c <= max_cop; c++) {
                if(a < max_alp) {
                    dp[a+1][c] = Math.min(dp[a+1][c], dp[a][c] + 1);                    
                }
                
                if(c < max_cop) {
                    dp[a][c+1] = Math.min(dp[a][c+1], dp[a][c] + 1);
                }
                
                
                for(int[] problem: problems) {
                    int alp_req = problem[0];
                    int cop_req = problem[1];
                    int alp_rwd = problem[2];
                    int cop_rwd = problem[3];
                    int cost = problem[4];
                    
                    if(alp_req <= a && cop_req <= c) {
                        int nalp = Math.min(max_alp, a + alp_rwd);
                        int ncop = Math.min(max_cop, c + cop_rwd);
                        dp[nalp][ncop] = Math.min(dp[nalp][ncop], dp[a][c] + cost);
                    }
                }
            }
        }
        
        
        return dp[max_alp][max_cop];
    }
}

 

 

아래 코드는 각각 알고력과 코딩력을 공부해서 올리는 방법을 나타냅니다.

if(a < max_alp) {
       dp[a+1][c] = Math.min(dp[a+1][c], dp[a][c] + 1);                    
    }
                
if(c < max_cop) {
       dp[a][c+1] = Math.min(dp[a][c+1], dp[a][c] + 1);
    }

 

해당 알고력과 코딩력을 도달하는데 필요한 최소시간을 계속 갱신합니다.

 

for(int[] problem: problems) {
          int alp_req = problem[0];
          int cop_req = problem[1];
          int alp_rwd = problem[2];
          int cop_rwd = problem[3];
          int cost = problem[4];
                    
          if(alp_req <= a && cop_req <= c) {
                 int nalp = Math.min(max_alp, a + alp_rwd);
                 int ncop = Math.min(max_cop, c + cop_rwd);
                 dp[nalp][ncop] = Math.min(dp[nalp][ncop], dp[a][c] + cost);
           }
}

 

풀 수 있는 문제를 선택하면서, 해당 알고력과 해당 코딩력을 도달하는데 걸리는 최소 횟수를 구합니다.

 

 

출력 결과

 

정리

완탐 시간 초과나면 바로 DP로 틉니다.