[boj] 12865. 평범한 배낭 (node.js)

문제 요약

[boj] 12865. 평범한 배낭 (node.js)

풀이

• dp 로 풀이하는 배낭 문제
• 정렬 없이, dp의 행/열로 물건의 개수, 무게를 제약으로 두고 값으로 가치를 계산
• dp[i][j] =
  • i개의 물건 (1~i 번째 물건)을 사용해서
  • 최대 j의 무게를 채울 수 있는
  • 가치의 최댓값
• 점화식 dp[i][j] = Math.max(dp[i][j], preValue + value);
  • 초기값 할당: dp[i][j] = dp[i-1][j] 할당해준 후 indexError 확인
    • 오류 없으면 점화식 실행 dp[i][j] = Math.max(dp[i][j], preValue + value);
    • indexError 시 continue해서 할당한 초기값 있는 상태로 스킵

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  const [N, K] = input().split(" ").map(Number);
  let arr = [];
  let dp = [];
  dp[0] = new Array(K + 1).fill(0);
  for (let i = 0; i < N; i++) {
    let [W, V] = input().split(" ").map(Number);
    arr.push([W, V]);
  }
  dynamic();
  console.log(dp[N][K]);

  function dynamic() {
    for (let i = 1; i <= N; i++) {
      dp[i] = [];
      dp[i][0] = 0;
      let weight = arr[i - 1][0];
      let value = arr[i - 1][1];
      for (let j = 1; j <= K; j++) {
        dp[i][j] = dp[i - 1][j];
        if (j - weight < 0) continue;
        let preValue = dp[i - 1][j - weight];
        dp[i][j] = Math.max(dp[i][j], preValue + value);
      }
    }
  }
};

let line = 0;
const input = () => stdin[line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});