[Java] Level 4. 서울에서 경산까지

Level 4. 서울에서 경산까지

 

문제출저: https://programmers.co.kr/learn/courses/30/lessons/42899

코딩테스트 연습 - 서울에서 경산까지 | 프로그래머스

DP로 해결한 문제. 이차원 배열에서 행이 도시, 열이 시간으로 생각하면 된다. 도시의 갯수는 travel.length, 시간은 0초부터 K초이기 때문에 int[][]dp = new int[length][K+1]로 생성.

 

dp[i][j]에는 첫번째 도시부터 i+1번째 도시 까지 도착하는 시간이 j분 만에 갈때 모을 수 있는 모금액의 액수가 들어간다.

 

if (k + travel[i][0] <= K) { // walk
  dp[i][k + travel[i][0]] = Math.max(dp[i][k + travel[i][0]], dp[i-1][k] + travel[i][1]);
  answer = Math.max(answer, dp[i][k + travel[i][0]]);
}

if (k + travel[i][2] <= K) { // bike
  dp[i][k + travel[i][2]] = Math.max(dp[i][k + travel[i][2]], dp[i-1][k] + travel[i][3]);
  answer = Math.max(answer, dp[i][k + travel[i][2]]);
}

이 알고리즘의 핵심부분이다. 다음 도시 까지 도착하는데 걸리는 시간과 모금액을 찾아 기록하는 부분이며

dp[i-1][k] != 0 인 지점은 이전도시까지 k초 걸려서 도착했을 때 모금한 액수가 들어있다. 이부분에서 다음도시로 가기 위한 시간과 모금액을 계산해서 저장해준다.

 

조건문 if는 시간을 초과하지 않는지 검사한다. 만약 시간을 초과하지 않는다면 해당 도시에 도착할 수 있을 시간에 총 모금될 수 있는 금액을 더한다. 그리고 최대 얻을 수 있는 모금액을 검사하고 갱신해준다.

 

class Solution {
    public int solution(int K, int[][] travel) {
        int length = travel.length;
        int[][] dp = new int[length][K + 1];
        int answer = 0;
        dp[0][travel[0][0]] = travel[0][1];
        dp[0][travel[0][2]] = travel[0][3];
        
        for (int i = 1; i < length; i++) {
            for (int k = 0; k <= K; k++) {
                if (dp[i-1][k] == 0) {
                    continue;
                }
                
                if (k + travel[i][0] <= K) { // walk
                    dp[i][k + travel[i][0]] = Math.max(dp[i][k + travel[i][0]], dp[i-1][k] + travel[i][1]);
                    answer = Math.max(answer, dp[i][k + travel[i][0]]);
                }
                
                if (k + travel[i][2] <= K) { // bike
                    dp[i][k + travel[i][2]] = Math.max(dp[i][k + travel[i][2]], dp[i-1][k] + travel[i][3]);
                    answer = Math.max(answer, dp[i][k + travel[i][2]]);
                }
                
            }
        }
        
        return answer;
    }
}