[백준] 14863번 서울에서 경산까지 C++ 코드

코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
struct info
{
  int wt, wm, bt, bm;
};

const int INF = 987654321;
int n, k,a,b,c,d,dp[103][100003];
vector<info> v;

int go(int idx, int ti) {
  // 시간이 오버되면 -INF 반환
  if(ti > k) return -INF;
  if(idx == n) return 0;
  int &ret = dp[idx][ti];
  if(ret != -1) return ret;
  int walk = go(idx + 1, ti + v[idx].wt) + v[idx].wm;
  int bike = go(idx + 1, ti + v[idx].bt) + v[idx].bm;
  // 걷는 게 더 수익이 높은지 자전거 타는 게 수익 높은지 비교
  ret = max(walk, bike);
  return ret;
}

int main() {
  cin >> n >> k;
  memset(dp, -1, sizeof(dp));
  for(int i = 0; i < n; i++) {
    cin >> a >> b >> c >> d;
    v.push_back({a,b,c,d});
  }
  cout << go(0,0) << '\n';
  return 0;
}

풀이

소요되는 시간과 인덱스를 상태로 하는 dp 테이블을 만들어주면 쉽게 해결할 수 있다. 0/1 냅색 문제랑 비슷한듯 다르다. 접근 방법 자체는 비슷하다. 어떤 방법으로 갔을 때 더 큰 값이 반환되는지 확인하고 저장해주면 된다.