[DP (동적 프로그래밍) / BOJ 14863 / C++] 서울에서 경산까지

https://www.acmicpc.net/problem/14863

14863번: 서울에서 경산까지

 

기본적인 dp 문제!

먼저 시간복잡도만 계산해보면 100개의 구간 각각이 2개씩 가능하므로, 2^100이라는 큰 수가 나온다.

 

따라서 DP를 써야할 수 밖에 없다.

 

그래프를 진행할수록 반드시 필요한 2가지 상태값이 있다.

 

1. 현재 구간 위치

2. 지금까지의 소요시간

 

이것을 바탕으로 해당 경로가 가질 수 있는 최대값을 유추할 수 있다.

 

다음처럼 그래프를 그려보자.

int형을 return하는 재귀함수를 짜보자. 큰 값만 결정하면 되기 때문에 max로 계속 update 해주면 된다.

 

#include <bits/stdc++.h>

using namespace std;

int N, K;
int wt, wm, bt, bm;
int dp[100001][101];
pair<int, int> w[101]; // 걸린시간 , 모금액
pair<int, int> b[101];

int go(int now_time, int now){ // 소요 시간, 현재 구간
    if(now_time>K) {return -100000000;} // 소요시간 넘어가면 종료
    if(now==N){return 0;} // 위치 도달시 종료
    
    int &mid = dp[now_time][now];
    
    if(mid) return mid;
    
    mid = max(go(now_time+w[now].first, now+1) + w[now].second, go(now_time+b[now].first, now+1) + b[now].second); // 걷기와 자전거타기 중에 max 선택
    
    return mid;
    
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> K;
    
    
    for(int i = 0 ; i < N ; i++){
        
        cin >> wt >> wm >> bt >> bm;
        w[i] = {wt, wm};
        b[i] = {bt, bm};
    }
    
    cout << go(0, 0) << '\n';
}