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

1. 문제 풀이

문제의 유형은 dynamic programming입니다. 문제를 읽다 보면 시간과 비용을 주고 조건에 맞춰 답을 출력하는 문제입니다. 시간+비용을 통해 knapsack problem임을 알 수 있습니다. 다른 응용이 없으므로 점화식을 세워서 풀어주시면 됩니다. 

저는 아래와 같이 테이블을 선언하여 풀었습니다.

 

d[i][j] = k : i 구간에서 j 시간이 걸렸을 때, 가능한 모금액의 최댓값 k

 

각 구간에는 도보 또는 자전거 2가지의 경우밖에 없으므로 적절하게 점화식을 세워서 테이블을 갱신하시면 됩니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';
int n, k;
pi w[105], b[105];
int d[105][100'005];
int main() {
  fastio(nullptr, false);
  cin >> n >> k;
  for(int i = 1; i <= n; i++) cin >> w[i].X >> w[i].Y >> b[i].X >> b[i].Y;
  d[1][w[1].X] = w[1].Y;
  d[1][b[1].X] = max(d[1][b[1].X], b[1].Y);
  for(int i = 1; i <= n-1; i++){
    for(int j = 0; j <= k; j++){
      if(!d[i][j]) continue;
      if(j+w[i+1].X <= k) d[i+1][j+w[i+1].X] = max(d[i+1][j+w[i+1].X], d[i][j] + w[i+1].Y);
      if(j+b[i+1].X <= k) d[i+1][j+b[i+1].X] = max(d[i+1][j+b[i+1].X], d[i][j] + b[i+1].Y);
    }
  }
  cout << *max_element(d[n], d[n]+k+1);
}

 

3. 제출 결과

 

주의 사항으로는 처음 주어진 도보 이동 시간과 자전거 이동 시간이 같은 경우 그중 최댓값을 가지게끔 구현해야 합니다. 

이 부분을 구현하지 못해서 29점을 받았습니다. 이로 인해, 제약 조건은 시간복잡도뿐만 아니라 논리적으로 틀린 경우에도 부분 점수를 받을 수 있다는 사실을 알 수 있었습니다.