[백준] - 12865 평범한 배낭 (node.js)

문제링크

풀이

너무 오랜만에 문제 풀어서 그런지 감이 잘 잡히지 않았다.
이 문제는 다이나믹 프로그래밍을 사용하는 문제였는데.. 다이나믹 프로그래밍과 한발짝 떨어지게 된 기분 ㅋㅎㅋㅎㅋㅎ.. 앞으로 열심히 해야겠다.

n과 k를 통해 이중 for문을 돌리면서 dp에 저장하는 방식으로 풀었다.

1부터 버틸 수 있는 무게까지 반복문을 돌면서 dp에 (이전에 저장한 가치)와 (지금 들어온 무게를 뺀 것의 가치+지금 들어온 무게의 가치)를 비교해 저장하는 방식이다. 문제 예제의 경우는 아래와 같다.

코드

// 평범한 배낭

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const arr = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, k] = arr.shift().split(" ").map(Number);

const dp = Array.from(Array(n + 1), () => new Array(k + 1).fill(0));

for (let i = 1; i <= n; i++) {
  const [w, v] = arr[i - 1].split(" ").map(Number);
  for (let j = 1; j <= k; j++) {
    dp[i][j] = dp[i - 1][j];
    if (j >= w) {
      console.log(i, j, dp[i][j], dp[i - 1][j - w] + v);
      dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w] + v);
    }
  }
}

console.log(dp[n][k]);

뭔가 다음에 봤을 때 풀 수 있을지 확실하지가 않은 거 같다.... 😅
아무래도 일주일?쯤 후에 다시 풀어봐야할 거 같다. (한 번 더 풀었다✅)