[프로그래머스] DP(7) 서울에서 경산까지

문제 설명

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

예를 들어 여행 루트가 다음과 같고 K = 1,650 일 때

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보다 작거나 같은 자연수입니다.

 

입출력 예

K	travel	return
1650	[[500, 200, 200, 100], [800, 370, 300, 120], [700, 250, 300, 90]]	660
3000	[[1000, 2000, 300, 700], [1100, 1900, 400, 900], [900, 1800, 400, 700], [1200, 2300, 500, 1200]]	5900

 

입출력 예 설명

입출력 예#1
앞서 설명한 예와 같습니다.

입출력 예#2
1, 4번 구간은 도보로 이동하고 2, 3번 구간은 자전거로 이동하여 모금액을 5,900원으로 하는 것이 가장 좋은 방법입니다. 이때 걸리는 시간은 3,000시간입니다.

 

풀이

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int dp[101][100001] = {0,}; // 모금액 저장 배열 dp[구간][이동시간] 0으로 초기화

int solution(int K, vector<vector<int>> travel) {
    int answer = 0;
    
    dp[0][travel[0][0]] = travel[0][1]; // 구간 1 도보 이동
    dp[0][travel[0][2]] = travel[0][3]; // 구간 1 자전거 이동
    
    for (int i = 1; i < travel.size(); i++) {
        for (int k = 0; k < K; k++) {
            
            if (dp[i-1][k] == 0) continue; // 걸린 시간이 아니면 pass
            
            /*
             * 기존 루트 + 도보 이동
             */
            if (travel[i][0] + k <= K) {
                // 이동 시간이 같으면 dp[i][travel[i][0]+k], dp[i-1][k] + travel[i]1[1] 중에 max값 저장
                // 이동 시간이 같지 않으면 dp[i][travel[i][0]+k] 값은 0 
                dp[i][travel[i][0]+k] = max(dp[i][travel[i][0]+k], dp[i-1][k] + travel[i][1]); 
                
                answer = max(answer, dp[i][travel[i][0]+k]); // 모금액 최댓값 update
            }

            /*
             * 기존 루트 + 자전거 이동
             */
            if (travel[i][2] + k <= K) {
                // 이동 시간이 같으면 dp[i][travel[i][2]+k], dp[i-1][k] + travel[i][3] 중에 max값 저장
                // 이동 시간이 같지 않으면 dp[i][travel[i][2]+k] 값은 0 
                dp[i][travel[i][2]+k] = max(dp[i][travel[i][2]+k], dp[i-1][k] + travel[i][3]);
                
                answer = max(answer, dp[i][travel[i][2]+k]); // 모금액 최댓값 update
            }
            
        }
    }
    return answer;
}

 

모든 루트를 탐색해야 한다.

(1) 도보

(2) 자전거 

하나의 구간마다 총 2가지의 이동 방식이 있기 때문에 2^n 개의 경로가 나온다.

 

dp[구간][이동시간] 을 나타내는 배열에 모금액 값을 저장한다.

 

for 문으로 0부터 K 값까지 순회하면서 dp[직전구간][이동시간] != 0일때,

그 값에 다음 구간 이동 시간을 더한다. (만약, 다음 루트 이동 시간이 K보다 크다면 이동 하지 않는다.) 

 

다음 구간 이동 시간이 전에 이동했던 시간과 같다면, 그 중 max 값을 저장한다. 

max(dp[i][travel[i][2]+k], dp[i-1][k] + travel[i][3]);

 

구간 이동 시에 모금 금액의 최댓값을 계속해서 update하여 최종 모금액 최댓값을 리턴한다.

 

해당 필기는 <TC 1>의 모든 경우의 이동 시간과 모금액을 계산한 것이다.

해당 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42899

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