[백준 12865번] DP(다이나믹 프로그래밍) - 평범한 배낭

✨ 문제 ✨

✨ 정답 ✨

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim();

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

const [N, K] = input.shift().split(' ').map((el)=>+el)
input = input.map((str) => str.split(' ').map((el)=>+el));

input.unshift(undefined);

const dp = [];
for (let i = 0; i <= N; i++) {
  dp.push(Array(K + 1).fill(0));
}

for (let t=1;t<=N;t++){
    const [W,V]=input[t];
    for (let k=0;k<=K;k++){
        if (k<W){
            dp[t][k]=dp[t-1][k];
        }else{
            dp[t][k]=Math.max(
                dp[t-1][k]
                ,dp[t-1][k-W]+V
            );
        }
    }

}
console.log(dp[N][K])

🧵 참고한 정답지 🧵

https://gywlsp.github.io/boj/12865/

💡💡 기억해야 할 점 💡💡

1. dp를 어떻게 잡을 것인가
2. dp[0], dp[1], dp[2] 이런 식으로 규칙을 찾을 것인지, dp[N]=dp[N-1]+? 이런 식으로 찾을지 확인해야 한다.
3. Math.max와 Math.min이 자주 사용되는 유형이다.