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

문제

서울에서 경산까지 여행을 하면서 모금 활동을 하려 합니다. 여행은 서울에서 출발해 다른 도시를 정해진 순서대로 딱 한 번 방문한 후 경산으로 도착할 예정입니다. 도시를 이동할 때에는 도보 혹은 자전거를 이용합니다. 이때 도보 이동에 걸리는 시간, 도보 이동 시 얻을 모금액, 자전거 이동에 걸리는 시간, 자전거 이동 시 얻을 모금액이 정해져 있습니다. K시간 이내로 여행할 때 모을 수 있는 최대 모금액을 알아보려 합니다.

예를 들어 여행 루트가 다음과 같고 K = 1,650 일 때
image.png
1, 2번 구간은 도보로, 3번 구간은 자전거로 이동해 모금액을 660으로 하는 것이 가장 좋은 방법입니다. 이때, 1,600시간이 소요됩니다.

solution 함수의 매개변수로 각 도시를 이동할 때 이동 수단별로 걸리는 시간과 모금액을 담은 2차원 배열 travel과 제한시간 K가 주어집니다. 제한시간 안에 서울에서 경산까지 여행을 하며 모을 수 있는 최대 모금액을 return 하도록 solution 함수를 작성하세요.

제한사항

  • travel 배열의 각 행은 순서대로 [도보 이동에 걸리는 시간, 도보 이동 시 얻을 모금액, 자전거 이동에 걸리는 시간, 자전거 이동 시 얻을 모금액]입니다.
  • travel 배열 행의 개수는 3 이상 100 이하인 정수입니다.
  • travel 배열에서 시간을 나타내는 숫자(각 행의 첫 번째, 세 번째 숫자)는 10,000 이하의 자연수, 모금액을 나타내는 숫자(각 행의 두 번째, 네 번째 숫자)는 1,000,000 이하의 자연수입니다.
  • K는 0보다 크고 100,000보다 작거나 같은 자연수입니다.

풀이

각 경로별로 현재까지 걸린 시간당 최대 모금액을 dp에 저장해서 풀었다.
문제에 나와있는 예제로 설명하자면, 첫번째 구간에서 도보로 이동하고 두번째 구간에서 자전거로 이동했다면 총 800분이 소요된다. 그럼 dp[1][800] = 520, 즉 두번째 구간에 총 800분이 걸렸을때 최대 모금액은 520원이 된다. 최대 모금액은 dp[0][800 - 현재 구간에서 걸리는시간] (이전 구간까지 모은 모금액) + 현재 구간에서 모을 수 있는 모금액 을 통해 구할 수 있다.
이 과정을 코드로 구현하면 아래와 같다.

for (int j = travel[i][2]; j <= K; j++) { // 현재 구간에서 걸리는 최소시간 ~ 최대시간
    // j = 현재 경로에서 걸린 시간 + 전까지의 경로에서 걸린시간 합계 
    // dp[i][j] 안에는 현재 경로까지 걸린시간에서 최대로 모을 수 있는 모금액 저장
    dp[i][j] = Math.max(dp[i-1][j - travel[i][0]] + 
                        travel[i][1], dp[i-1][j - travel[i][2]] + travel[i][3]); 
}   

마지막으로 dp의 끝에 저장된 모금액 중 최대값을 반환하면 끝!

코드

class Solution {
    public int solution(int K, int[][] travel) {
        int answer = 0;
        int[][] dp = new int[travel.length][K + 1]; //각 경로의 현재까지 걸린 시간별로 모은 모금액을 저장할 배열
        dp[0][travel[0][0]] = travel[0][1];
        dp[0][travel[0][2]] = travel[0][3];

        for (int i = 1; i < travel.length; i++) {
            for (int j = travel[i][2]; j <= K; j++) { 
                if (j - travel[i][0] < 0) { //array index out of bounds exception handling
                    if (dp[i-1][j - travel[i][2]] != 0) {
                        dp[i][j] = dp[i-1][j - travel[i][2]] + travel[i][3]; 
                    }
                    continue;
                }
                // 여행지를 모두 들리지 않는 케이스는 넘어간다
                if (dp[i-1][j - travel[i][0]] == 0 && dp[i-1][j - travel[i][2]] == 0) {
                    continue;
                }
                else if (dp[i-1][j - travel[i][2]] == 0) {
                    dp[i][j] = dp[i-1][j - travel[i][0]] + travel[i][1]; 
                    continue;
                }
                // j = 현재 경로에서 걸린 시간 + 전까지의 경로에서 걸린시간 합계 
                // dp[i][j] 안에는 현재 경로까지 걸린시간에서 최대로 모을 수 있는 모금액 저장
                dp[i][j] = Math.max(dp[i-1][j - travel[i][0]] + travel[i][1], dp[i-1][j - travel[i][2]] + travel[i][3]); 
            }    
        }
        for (int i = 0; i <= K; i++) {
            answer = Math.max(answer, dp[travel.length - 1][i]);
        }
        return answer;
    }
}