정올 3074 / 백준 14863 서울에서 경산까지

algorithm DP

 

해설

이문제를 2차원 배열로 만들수 있는 근거

1. 도시 수가 최대 100

2. 모금액이 100,000

 

100 * 100,000 = 100,000,000 메모리 초과 X

 

DP 정의 : i번째 도시에서 모금액 j을 모을때 최소금액

점화식은 코드참고

#include<bits/stdc++.h>
#define LM 100000+10
#define INF 199999999
using LL = long long;
using namespace std;
 
int N,K;
int dp[100 + 10][LM];
struct data{
    int time,money;
};
 
data bike[100 + 10],step[100 + 10];
 
void input(){
    scanf("%d %d",&N,&K);
    for(int i = 1 ; i <= N ; i ++){
        scanf("%d %d %d %d",&step[i].time,&step[i].money,&bike[i].time,&bike[i].money);
    }
}
 
void f(){
    dp[1][step[1].time] = step[1].money , dp[1][bike[1].time] = bike[1].money;
    for(int i = 2 ; i <= N ; i ++){
        for(int j = 1 ; j <= K ; j ++){
            if(dp[i - 1][j] != 0){
                if(j + step[i].time <= K) dp[i][j + step[i].time] = max(dp[i][j + step[i].time],dp[i - 1][j] + step[i].money);
                if(j + bike[i].time <= K) dp[i][j + bike[i].time] = max(dp[i][j + bike[i].time],dp[i - 1][j] + bike[i].money);
            }
        }
    }
    int ans = 0;
    for(int i = 1 ; i <= K; i ++){
        ans = max(ans,dp[N][i]);
    }
    printf("%d",ans);
}
 
int main(){
    //freopen("input.txt","r",stdin);
    input();
    f();
    return 0;
}