백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 12865 , 평범한 배낭

백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 12865 , 평범한 배낭

 

 

 

문제 출처

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

12865번: 평범한 배낭

 

 

풀이

 

이 풀이는 다음의 로직을 담고 있다.

 

1. 우선 각 물품의 무게와 가치값을 arr 배열에 담아준다.

 

2. 이제 각 물품이 어떤 물품들이랑 같이 담겨졌을때, 가장 최대의 가치값을 가지는지 체크를 해준다.

 

 

 

 

K가 10일 때 무게가 4인 물품은 더해질 수 있는 무게인 6 5 4 3 2 1 0 인 물품들에 차례로 더해가면서 비교하고 

 

check 배열의 해당인덱스에 담긴 값은 최대값으로 계속 초기화해 나아간다.

 

 

3. 최종적으로 check 배열 끝자리에는 K이내의 최대 가치 값이 담기게 된다.

 

 

 

 

정답

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const cal = (Arr) => {
  Arr.map((v) => {
    let [a, b] = v;
    for (let i = K; i > a - 1; i--)
      check[i] = Math.max(check[i], check[i - a] + b);
  });
  return check[K];
};

const [N, K] = input.shift().split(" ").map(Number);
let check = [...new Array(K + 1)].fill(0);
let arr = [];
input.map((v) => {
  let [w, g] = v.trim().split(" ").map(Number);
  arr.push([w, g]);
});

console.log(cal(arr));