백준 14863 서울에서 경산까지

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

문제

모금 활동을 하면서 드는 비용과 이에 대한 가치를 가지고 있는 knapsack 문제의 dp 문제이다.

배낭 문제란?

n개의 물건과 배낭이 있을 때, 물건에는 각각 가치와 무게가 존재하고 가방은 최대 수용 무게가 정해져 있다. 이 상태에서 가방에 넣을 수 있는 물건의 조합 중 가장 큰 가치를 가질 수 있는 조합을 고르는 문제이다

접근방법

완탐으로 풀게 되면 O(2^n)의 시간 복잡도가 나오고, 그래프 탐색으로 풀면 서브태스크에서 막히게 된다. 또한 각 도시마다 양방향으로 이동할수 있는 것이 아니고, 무조건 오른쪽방향으로 계속 이동해야 하기 떄문에 knapsack문제를 여기에 적용할 수 있다.

점화식

dp[i][j] = i번째 순서에서 j의 시간이 걸렸을 떄 가질 수 있는 최대 비용 i번째 순서에서 j의 시간이 걸렸을 때 가질 수 있는 최대 비용을 dp[i][j]에 두게 되면 이전의 순서와 시간에 접근해서 가능한 조합의 경우의 수가 있는 경우 계속해서 이를 업데이트하면서 최댓값을 계속해서 갱신해나갈 수 있다.

풀이

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
const [N, K] = inputs[0].split(" ").map(Number);
const info = inputs.slice(1).map((line) => line.split(" ").map(Number));
 
const dp = Array.from({ length: N }, () => Array(K + 1).fill(0));
 
dp[0][info[0][0]] = info[0][1];
dp[0][info[0][2]] = Math.max(dp[0][info[0][2]], info[0][3]);
 
//i번째 도시까지 j분이 걸릴 때 가질 수 있는 최대 비용
for (let i = 1; i < N; i++) {
  const [footTime, footCost, bikeTime, bikeCost] = info[i];
  const minTime = Math.min(footTime, bikeTime);
  for (let j = 0; j <= K - minTime; j++) {
    if (dp[i - 1][j]) {
      const tempFootTime = j + footTime;
      const tempBikeTime = j + bikeTime;
      const tempFootCost = dp[i - 1][j] + footCost;
      const tempBikeCost = dp[i - 1][j] + bikeCost;
      if (tempFootTime <= K) {
        dp[i][tempFootTime] = Math.max(dp[i][tempFootTime], tempFootCost);
      }
      if (tempBikeTime <= K) {
        dp[i][tempBikeTime] = Math.max(dp[i][tempBikeTime], tempBikeCost);
      }
    }
  }
}
console.log(Math.max(...dp[N - 1]));
 

값의 갱신의 경우 이전 순서에서 같은 시간의 값에 새롭게 가려는 도시의 비용을 합쳐서 계산하면 되며, 걸어서 갈 때와 자전거를 타고 갈 경우를 각각 계산해서 최댓값을 갱신해야 한다. 여기서 K이하로 조건식을 넣지 않으면 원래의 배열 사이즈를 초과해서 접근할 뿐만 아니라 가능한 시간을 초과한다는 소리이므로 갱신이 이루어지면 안될 값이기 때문에 넣어야 한다.