[프로그래머스/level 3] 코딩 테스트 공부 - 118668 (Java)

[level 3] 코딩 테스트 공부 - 118668

문제 링크

프로그래머스

 

풀이

DP를 이용해 해당 문제를 해결할 수 있다.

먼저 가능한 선택지는 3가지 이다.

 

1. 1시간을 사용, `alp` 1 늘리기
2. 1시간을 사용, `cop` 1 늘리기
3. 문제를 해결하여 주어진 `cost`를 사용, `alp_rwd`, `cop_rwd` 만큼 늘리기

row를 `alp`, col을 `cop`으로 두고 `[alp][cop]`에 시간(`cost`)을 저장하여 DP를 수행한다.

각 [알고력, 코딩력]에 도달하기 위한 경우의 수 중 cost가 가장 적은 것을 선택한다.

현재 `[alp][cop]`에서 

1. 1시간을 사용, `alp` 1 늘리기
   `dp[alp+1][cop]`와 `dp[alp][cop]+1`을 비교하여 작은 값을 선택한다.
2. 1시간을 사용, `cop` 1 늘리기
   `dp[alp][cop+1]`와 `dp[alp][cop]+1`을 비교하여 작은 값을 선택한다.
3. 문제를 해결하여 주어진 `cost`를 사용, `alp_rwd`, `cop_rwd` 만큼 늘리기
   `dp[alp+alp_wrd][cop+cop_rwd]`와 `dp[alp][cop]+cost`를 비교하여 작은 값을 선택한다.

* 최소 값을 비교하여 저장해야하므로, dp 배열의 초기 값을 큰 값으로 바꿔두자! 

해당 과정을 거친 후 주어진 문제 중 alp_req와 cop_req가 가장 클 때의 시간을 return 한다.

 

 

코드

import java.util.*;

class Solution {
    public int solution(int alp, int cop, int[][] problems) {
        int maxal = Math.max(alp, Arrays.stream(problems).mapToInt(p -> p[0]).max().orElse(0));
        int maxco = Math.max(cop, Arrays.stream(problems).mapToInt(p -> p[1]).max().orElse(0));

        int[][] dp = new int[maxal + 1][maxco + 1];
        Arrays.stream(dp).forEach(i -> Arrays.fill(i, 3151)); //dp배열 큰 값으로 초기화
        dp[alp][cop] = 0;  // 시작점 초기화

        for (int al = alp; al <= maxal; al++) {
            for (int co = cop; co <= maxco; co++) {
                // 한 시간씩 기다려서 alp 또는 cop 1 증가
                if (al < maxal) dp[al + 1][co] = Math.min(dp[al + 1][co], dp[al][co] + 1);
                if (co < maxco) dp[al][co + 1] = Math.min(dp[al][co + 1], dp[al][co] + 1);

                // 문제 풀었을 때 경험치 증가
                for (int[] p : problems) {
                    if (al >= p[0] && co >= p[1]) {
                        int a = Math.min(maxal, al + p[2]);
                        int c = Math.min(maxco, co + p[3]);
                        dp[a][c] = Math.min(dp[a][c], dp[al][co] + p[4]);
                    }
                }
            }
        }

        return dp[maxal][maxco];
    }
}