프로그래머스 - 코딩테스트 연습(Java)

DP 문제입니다.

 

문제와 초기 알고력과 코딩력이 주어집니다.

알고력과 코딩력의 증가 방법은 다음 두 가지와 같습니다.

1. 1초마다 알고력 혹은 코딩력을 증가시킬 수 있습니다.
2. 문제를 풀어 알고력과 코딩력을 증가시킬 수 있습니다.

 

DP 문제인 것만 알면, 해결 방법은 간단합니다.

초기 알고력과 코딩력을 1씩 증가 시킴과 동시에, 풀 수 있는 문제를 확인하면 됩니다.

알고력을 N, 코딩력을 M, 문제를 P라고 하면 시간복잡도는 O(NMP)입니다.

최대 범위를 기준으로 시간복잡도를 계산하면 150*150*100 = 2,250,000이므로 시간 내에 풀 수 있습니다.

 

주의해야 할 점은 증가되는 알고력 및 코딩력이 배열의 범위를 벗어날 수 있기 때문에 범위를 벗어 날 경우 최대치로 갱신해야 합니다.

 

[구현 코드]

class Solution {
    private static int[][] dp;
    private static final int MAX = Integer.MAX_VALUE;

    public int solution(int alp, int cop, int[][] problems) {
        int maxAlp = 0;
        int maxCop = 0;

        for (int[] problem : problems) {
            maxAlp = Math.max(maxAlp, problem[0]);
            maxCop = Math.max(maxCop, problem[1]);
        }

        dp = new int[maxAlp+2][maxCop+2];

        // 범위 넘어서지 않게
        if(alp > maxAlp){
            alp = maxAlp;
        }else if(cop > maxCop){
            cop = maxCop;
        }

        for(int i=alp; i<maxAlp+1; i++){
            for(int j=cop; j<maxCop+1; j++){
                dp[i][j] = MAX;
            }
        }

        dp[alp][cop] = 0;
        for(int i=alp; i<maxAlp+1; i++){
            for(int j=cop; j<maxCop+1; j++){
                // 1초 마다 코딩력 증가
                dp[i][j+1] = Math.min(dp[i][j+1], dp[i][j]+1);

                // 1초 마다 알고력 증가
                dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j]+1);

                for (int[] problem : problems) {
                    int alpReq = problem[0];
                    int copReq = problem[1];
                    int alpRwd = problem[2];
                    int copRwd = problem[3];
                    int cost = problem[4];

                    // 현재 알고력 및 코딩력으로 문제를 풀 수 있을 때
                    if(i>= alpReq && j>=copReq) {
                        int improveAlp = i+alpRwd;
                        int improveCop = j+copRwd;

                        if ((improveAlp >= maxAlp) && (improveCop >= maxCop)) {
                            // 해당 문제를 풀고 증가된 두 능력이 모두 목표 이상인 경우
                            // 최대 범위의 최솟값 갱싱
                            dp[maxAlp][maxCop] = Math.min(dp[maxAlp][maxCop], dp[i][j] + cost);
                        } else if (improveAlp >= maxAlp) {
                            // 증가된 알고력만 최대 범위인 경우
                            dp[maxAlp][improveCop] = Math.min(dp[maxAlp][improveCop], dp[i][j] + cost);
                        } else if (improveCop >= maxCop) {
                            dp[improveAlp][maxCop] = Math.min(dp[improveAlp][maxCop], dp[i][j] + cost);
                        } else{
                            // 둘 다 넘어서지 못할 경우
                            dp[improveAlp][improveCop] = Math.min(dp[improveAlp][improveCop], dp[i][j] + cost);
                        }
                    }
                }
            }
        }

        return dp[maxAlp][maxCop];
    }
}