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

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

---

풀이

대충 훑고 재밌어보여서 골랐는데 어쩌다보니 2연속 DP 문제를 풀게 되었다😂

 

이 문제에서는 현재 알고력과 현재 코딩력, 그리고 현재 알고력과 현재 코딩력까지 도달하기 위한 최단 시간을 저장해야 한다.
따라서 dp배열은 dp[알고력][코딩력] = 최단 시간의 형태가 된다.

 

DP 문제라고 생각한 이유는, dp[알고력][코딩력] = k의 값을 다음에 다시 재활용하기 때문이다.
실제 점화식을 세워보면, 다음 문제의 답을 구할 때 이전 문제의 답 k가 재활용된다는 것을 확인할 수 있다.

 

(1) 점화식 세우기

현재 알고력이 i, 현재 코딩력이 j, dp[i][j] = k라고 가정하면 아래와 같은 점화식을 세울 수 있다.

 

// 1. 알고력을 높이는 경우: dp[i+1][j] = Math.min(k+1, dp[i+1][j])
// 2. 코딩력을 높이는 경우: dp[i][j+1] = Math.min(k+1, dp[i][j+1])
// 3. k번째 문제를 풀 수 있는 경우: 
// dp[i+problems[k][2]][j+problems[k][3]] = Math.min(k+problems[k][4], dp[i+problems[k][2]][j+problems[k][3]])

 

 

i,j,k에 대해 3중 for문을 돌려주면 된다.

 

(2) 초기화

문제에서 주어지는 알고력과 코딩력의 범위는 최대 150이므로, dp[i][k]의 값은 최대 300이다.
따라서 dp[0][0]부터 dp[alp][cop]까지는 0으로, 그 외에는 300으로 초기화해주면 된다.

 

(3) 예외 케이스

1. 초기 알고력과 코딩력으로 모든 문제를 풀 수 있는 경우

문제에서 요구하는 최대 알고력, 최대 코딩력을 초기 알고력, 초기 코딩력과 비교하여, 초기값이 클 경우 바로 0을 리턴하면 된다.

 

2. 높인 알고력, 코딩력이 최대값보다 큰 경우

아래와 같이 인덱스 검사를 진행하면 된다.

 

// maxAlp = Math.max(문제에서 요구하는 최대 알고력, 초기 알고력);
// maxCop = Math.max(문제에서 요구하는 최대 코딩력, 초기 코딩력);

int nextAlp = Math.min(maxAlp, i+problems[k][2]);
int nextCop = Math.min(maxCop, j+problems[k][3]);
dp[nextAlp][nextCop] = Math.min(dp[nextAlp][nextCop], dp[i][j]+problems[k][4]);

 

주의할 점은, nextAlp와 nextCop의 최대 범위를 300이 아닌 maxAlp, maxCop로 제한해야 한다는 점이다.

 

maxAlp와 maxCop가 각각 20이고, 1번 문제를 풀었을 때 2만큼의 시간을 들여 알고력 4, 코딩력 2를 얻을 수 있다고 가정해보자.
(풀 수 있는 다른 문제는 없다고 가정한다.)

 

dp[17][19]=5인 상황이라면, 1번 문제를 풀면 문제에서 요구하는 능력치를 채울 수 있으므로 답은 7이 되어야 한다.

하지만 최대 범위를 300으로 두면 dp[21][21]만 7로 갱신되고, 우리가 구하는 값인 dp[20][20]은 갱신되지 않는다.

따라서 dp[21][21] 대신 dp[20][20]이 갱신되도록 하기 위해, nextAlp와 nextCop의 최대 범위를 maxAlp, maxCop로 제한하는 것이다.

 

---

전체 코드

 

import java.util.*;

class Solution {
    int[][] dp;
    int MAX = 150;
    int maxAlp=0, maxCop=0;
    public int solution(int alp, int cop, int[][] problems) {
        for(int i=0; i<problems.length; i++) {
            maxAlp = Math.max(maxAlp, problems[i][0]);
            maxCop = Math.max(maxCop, problems[i][1]);
        }
        if(alp>=maxAlp && cop>=maxCop) return 0;

        dp = new int[MAX+1][MAX+1];
        for(int i=0; i<dp.length; i++) {
            Arrays.fill(dp[i], MAX*2);
        }
        for(int i=0; i<=alp; i++) {
            for(int j=0; j<=cop; j++) {
                dp[i][j] = 0;
            }
        }

        for (int i=0; i<=MAX; i++) {
            for (int j=0; j<=MAX; j++) {
                for(int k=0; k<problems.length; k++) {
                    // 1. 알고력 높이기
                    if(i>0) {
                        dp[i][j] = Math.min(dp[i][j], dp[i-1][j]+1);
                    }
                    // 2. 코딩력 높이기
                    if(j>0) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][j-1]+1);
                    }

                    // 3. k번째 문제 풀기
                    if(i>=problems[k][0]&&j>=problems[k][1]) {
                        int nextAlp = Math.min(maxAlp, i+problems[k][2]);
                        int nextCop = Math.min(maxCop, j+problems[k][3]);
                        dp[nextAlp][nextCop] = Math.min(dp[nextAlp][nextCop], dp[i][j]+problems[k][4]);
                    }
                }


            }
        }

        return dp[maxAlp][maxCop];
    }
}