[BOJ] 백준 14863. 서울에서 경산까지 (Gold IV)

추천받은 문제 중 하나.

문제는 아래와 같다.

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

14863번: 서울에서 경산까지

---

의식의 흐름 및 해설

처음엔 평범한 knapsack인줄 알았는데,

생각해보니 자전거를 탈지, 도보로 갈지 선택을 해야되기 때문에 모든 경우를 선택하는 문제가 아니므로 knapsack dp가 아니었다.

 

따라서 top-down이든, bottom-up이든 시간복잡도 상 큰 차이가 없기 때문에 탑다운으로 풀었으며,

N번째까지 도달하지 못하는 경우에 답이 0 초과가 되는 것을 막기 위해 초기값을 ret=-INF로 설정해주었다.

 

knapsack과 헷갈리지 않으면 무난한 dp 문제.

---

코드

#include <bits/stdc++.h>
#define sz(v) (int)v.size()
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int,pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 103;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int N,K,d[MAX][100003],a[2][MAX],w[2][MAX];
int dp(int cur, int t){
    if(cur>=N)return 0;
    int& ret=d[cur][t];
    if(~ret)return ret;
    ret=-INF;
    if(t>=a[0][cur]){
        ret=max(ret, dp(cur+1,t-a[0][cur])+w[0][cur]);
    }
    if(t>=a[1][cur]){
        ret=max(ret, dp(cur+1, t-a[1][cur])+w[1][cur]);
    }
    return ret;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin>>N>>K;
    for(int i=0;i<N;i++){
        for(int j=0;j<2;j++){
            cin>>a[j][i]>>w[j][i];
        }
    }
    memset(d,-1,sizeof(d));
    cout<<dp(0,K);
}

---

knapsack의 특징을 잘 몰랐을 때 이 문제를 봤다면 큰 도움이 됐을 듯하다.

그만큼 좋다고 생각되는 문제 :)