서울에서 경산까지 - level 4

해결방법

2차원 dp로 해결하였다. i는 도시, j는 시간을 의미한다.

 int dp[101][100010];

점화식은 아래와 같다. k는 이전도시까지의 시간이다. 이전도시 시간과 + 현재도시 시간(걷는 방법과 자전거 2가지 모두)에 이전 도시까지 + k번째 기부금(걷는 방법과 자전거 2가지 모두)값의 넣는다.
$$ dp[i][k + 현재도시 시간] = max(dp[i][k + 현재도시 시간], dp[i-1][k] + k번째 기부금) $$
하지만, K(전체시간)을 넘으면 안되므로 예외처리를 해줘야 한다.

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

전체코드

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int dp[101][100010];
int solution(int K, vector<vector<int>> travel) {
    int answer = 0;
    dp[0][travel[0][0]] = travel[0][1];
    dp[0][travel[0][2]] = travel[0][3];
    for(int i = 1; i < travel.size(); ++i) {
        for(int k = 0; k <= K; ++k) {
            if(dp[i-1][k] == 0) continue;
            if(k + travel[i][0] <= K) {
                dp[i][k+travel[i][0]] = max(dp[i][k+travel[i][0]], dp[i-1][k] + travel[i][1]);
                answer = max(answer, dp[i][k+travel[i][0]]);
            }
            if(k + travel[i][2] <= K) {
                dp[i][k+travel[i][2]] = max(dp[i][k+travel[i][2]], dp[i-1][k] + travel[i][3]);
                answer = max(answer, dp[i][k+travel[i][2]]);
            }
        }
    }
    return answer;
}