[백준15486_자바스크립트(javascript)] - 퇴사2

🔴 문제

퇴사2

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [n, ...works] = fs.readFileSync(path).toString().trim().split('\n');
const N = Number(n);
const T = [];
const P = [];
const dp = Array(N + 1).fill(0);

for (const work of works) {
  const [t, p] = work.split(' ').map(Number);
  T.push(t);
  P.push(p);
}

for (let i = N - 1; i >= 0; i--) {
  if (i + T[i] <= N) {
    dp[i] = Math.max(dp[i + 1], dp[i + T[i]] + P[i]);
  } else {
    dp[i] = Math.max(dp[i + 1]);
  }
}

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

🟢 풀이

⏰ 소요한 시간 : -

퇴사랑 똑같지만 N의 범위만 다른 문제다.
이전 포스팅에서도 풀이 했듯이 N의 범위가 커졌기에 DP로만 풀이가 가능하다. 무서운 사실은 DP로 두번째 푸는것임에도 불구하고 한번에 못풀었다.
점화식을 다시한번 세워보자면 (역으로 풀이한다는 가정하에) 상담을 할지 말지만 결정해주면 된다.
만약 상담을 안한다면, 그 다음날이랑 급여가 같을 것이고
상담을 한다면 dp[i + T[i]] + P[i]가 최대 급여가 될 것이다.
사고가 뻗어나가기 너무 어렵다. ㅠㅠ

🔵 Ref

[백준14501_자바스크립트(javascript)] - 퇴사