99클럽 코테 스터디 42일차 TIL [DP]

- 오늘의 학습 키워드 : dp

[문제 이름 : 코딩 테스트 공부 (프로그래머스 118668, Lv 3)]

문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/118668

내가 작성한 코드는 아래와 같다.

import java.util.*;

class Solution {
    public int solution(int alp, int cop, int[][] problems) {
        int maxAlp = 0, maxCop = 0;
        
        for(int[] problem: problems) {
            maxAlp = Math.max(maxAlp, problem[0]);
            maxCop = Math.max(maxCop, problem[1]);
        }
        // 초기값이 이미 목표를 넘었으면, 0 반환해야 함
        alp = Math.min(alp, maxAlp);
        cop = Math.min(cop, maxCop);
        
        // dp[i][j] : 알고리즘 숙련도 i, 코딩 숙련도 j일 때 목표 달성을 위해 걸리는 최소 시간
        int[][] dp = new int[maxAlp+1][maxCop+1];
        for(int i=0; i<=maxAlp; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[alp][cop] = 0;
        
        for(int i=alp; i<= maxAlp; i++) {
            for(int j=cop; j<=maxCop; j++) {
                // 알고리즘 직접 공부하여 숙련도 1 증가하는 경우
                if (i+1 <= maxAlp) {
                    dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j]+1);
                }
                // 코딩 직접 공부하여 숙련도 1 증가하는 경우
                if (j+1 <= maxCop) {
                    dp[i][j+1] = Math.min(dp[i][j+1], dp[i][j]+1);
                }
                // 주어진 문제를 통해 숙련도가 증가하는 경우
                for(int[] problem : problems) {
                    if(i >= problem[0] && j >= problem[1]) {
                        int ni = Math.min(maxAlp, i + problem[2]);
                        int nj = Math.min(maxCop, j + problem[3]);
                        dp[ni][nj] = Math.min(dp[ni][nj], dp[i][j] + problem[4]);
                    }
                }
            }
        }
        return dp[maxAlp][maxCop];
    }
}

[풀이 과정]

1. 배열의 크기를 잡기 위해, 최대 알고력과 최대 코딩력을 계산한다.

2. 이미 alp와 cop가 최대값보다 크다면, 해당 값들을 고려할 필요가 없으므로, alp와 cop값을 최대 값으로 제한한다.

3. 2차원 배열 dp를 만들어준다. 이때 dp[i][j]에 해당하는 값은 알고리즘 숙련도 i, 코딩 숙련도 j일 때 목표 달성을 위해 걸리는 최소 시간을 의미한다.

4. 처음 갖고 있는 알고력과 코딩력으로 문제를 해결할 수 있는 시간은 0이므로, dp[alp][cop]=0을 선언한다.

5. 반복을 돌면서, 직접 공부할 때에 따라서 숙련도를 증가시켜준다. 만약 문제를 풀 수 있다면, 해당 문제의 알고력과 코딩력을 비교하여 dp배열을 갱신한다.

 

풀이 시간 : 2시간

참고 블로그 : https://sedangdang.tistory.com/273