[프로그래머스/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 한다.

 

 

코드

java

닫기

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];
    }
}