프로그래머스 : 서울에서 경산까지

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42899

프로그래머스

 문제 설명 

 

서울에서 경산까지 여행을하는데 중간에 도시를 들릴때마다 걸어가거나 자전거를 타고갈수있다.

걸어갈때와 자전거를 타고갈때 걸리는 시간과 얻을수있는 모금액은 다르다.

시간이 제한되어있을때 얻을 수있는 최대의 모금액을 구하여라 ..

 

 알고리즘  

 

DP함수를 시간을 기준으로 만들고 안에 내용은 모금액을 기준으로 채우면 된다.

어려운 문제였고 아직도어려워서 헷갈리긴한다

 

 

 

DP 함수는 이런식으로 채워진다

 소스코드 

 

 

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