[백준7579_자바스크립트(javascript)] - 앱

🔴 문제

앱

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n, m], M, C] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((line) => line.split(' ').map(Number));

const sumC = C.reduce((pre, cur) => pre + cur);
const dp = Array(sumC + 1).fill(0);

for (let a = 0; a < n; a++) {
  const memory = M[a];
  const cost = C[a];

  for (let i = sumC; i >= cost; i--) {
    dp[i] = Math.max(dp[i], dp[i - cost] + memory);
  }
}

console.log(dp.findIndex((it) => it >= m));

🟢 풀이

⏰ 소요한 시간 : -

냅색 유형의 문제!
앱을 비활성화 했을 때 얻을수 있는 메모리 공간을 M배열, 앱을 비활성화 했을 때 발생하는 비용을 C배열로 받았다.
만약 모든 앱을 다 비활성화 하는 경우가 발생할 수 있는 비용의 최대값이므로 C배열을 모두 합해 sumC변수에 넣고, 이 크기만큼의 dp배열을 만들어줬다.
dp[n]는 내가 n만큼의 비용을 소모했을 경우 얻을 수 있는 메모리 공간의 최대값이 되는 것이다.
그 후 앱의 개수인 n개 만큼 반복하며 각 cost에 맞게 앱을 비활성화 해야 비용이 높은지, 아닌지를 구분해 dp 배열을 채워준다
이 때 sumC부터 시작해서 내가 앱을 비활성화 할 수 있는 최소의 비용 cost까지 반복하면서 dp를 껐을 때와, 안껐을 때 중 얻을 수 메모리 공간의 최대값으 구해주면 된다.

마지막으로 정답을 출력할때는 dp배열의 맨 앞부터 목표 메모리 공간인 m을 넘는 첫 인덱스를 반환해주면 된다.

🔵 Ref