[BOJ/백준][Gold4] 14863 : 서울에서 경산까지 (C++)

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

14863번: 서울에서 경산까지

 

 

[난이도] Gold4
[유형] DP

[풀이]
전형적인 DP 문제

DP(n,k): 현재 k시간을 썼고 n번 길을 지나야 할때 얻을 수 있는 최대 모금액
점화식 => DP(n,k) =max( DP(n+1,k+[n번째 도보 시간])+[n번째 도보 모금액] ,
DP(n+1,k+[n번째 자전거 시간])+[n번째 자전거 모금액] )

 

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int N,K,pt[100][2],pr[100][2],dp[100][100001];
int sol(int n,int k){
    if(k>K) return -9e8;
    if(n==N) return 0;
    int& ret = dp[n][k];
    if(ret!=-1) return ret;
    ret = max(sol(n+1,k+pt[n][0])+pr[n][0],sol(n+1,k+pt[n][1])+pr[n][1]);
    return ret;
}
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++) scanf("%d%d%d%d",&pt[i][0],&pr[i][0],&pt[i][1],&pr[i][1]);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,0));
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/14863.cpp