🎲 백준 15486번 퇴사2

백준 15486번

🧸 전에 "퇴사" 문제를 풀었는데 스스로 못풀었어서 퇴사2에 도전해봤다.
🧸 내가 스스로 쓴 코드는 시간초과가 발생했다. "퇴사"와 "퇴사2"의 차이는 N의 범위였다. 내 코드는 "퇴사"문제는 풀 수 있었지만 "퇴사2"는 풀지못했다. 전에 혼자 못풀던 "퇴사"문제를 스스로 푼건 좋았지만 "퇴사2"는 해내지 못한것이 아쉽다.
💡 max를 따로 저장하면서 풀면 반복문을 한 번 더 사용하지 않아도 풀 수 있다.
🧸 따로 저장하면 된다는 생각은 했는데 내 머릿속에서는 안되는 것 같은데..?로 끝났다. 조금 더 차분히, 침착하게 생각했으면 풀 수 있지 않았을까 생각한다.

정답 코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input.shift();
const dp = new Array(N + 1).fill(0);
const schedule = input.map((item) => item.split(" ").map(Number));

let max = 0;
for (let i = 0; i < N; i++) {
  const [day, cost] = schedule[i];
  max = Math.max(dp[i], max);
  if (i + day <= N) dp[i + day] = Math.max(dp[i + day], max + cost);
}

console.log(Math.max(...dp));

시간초과 코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input.shift();
const dp = new Array(N).fill(0);
const schedule = input.map((item) => item.split(" ").map(Number));

for (let i = 0; i < N; i++) {
  const [day, cost] = schedule[i];
  if (i + day - 1 < N) {
    dp[i] += cost;
    if (i + day < N) {
      for (let j = i + day; j < N; j++) {
        dp[j] = Math.max(dp[i], dp[j]);
      }
    }
  }
}

console.log(Math.max(...dp));