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

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

코딩테스트 연습 - 서울에서 경산까지

 

동적계획법 문제

 

 

 

 

 

 

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#define INF 987654321

using namespace std;

int k, length;
int cache[101][100001];

int getMax(const vector<vector<int>>& travel, int index, int time) {
    if(time > k) return -INF;
    if(index == length) return 0;
    
    
    int& ret = cache[index][time];
    if(ret != -1) return ret;
    
    ret = 0;
    
    int a = getMax(travel, index + 1, time + travel[index][0]) + travel[index][1];
    int b = getMax(travel, index + 1, time + travel[index][2]) + travel[index][3];
    
    ret = max(a, b);
    return ret;
}


int solution(int K, vector<vector<int>> travel) {
    int answer = 0;
    k = K;
    length = travel.size();
    
    memset(cache, -1, sizeof(cache));
    
    answer = getMax(travel, 0, 0);
    
    return answer;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~