Baekjoon 15486번 퇴사 2

문제

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

걸린 시간

- 실패

풀이

JavaScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map(s => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

let n = parseInt(input());

const a = []
for(let i = 0; i < n; i++){
  a.push(input().split(' ').map(Number));
}

const dp = Array(n+1).fill(0);

for(let i = 0; i < n; i++){
  const [t, p] = a[i];
  if(i+t <= n) dp[i+t] = Math.max(dp[i+t], dp[i]+p);
  dp[i+1] = Math.max(dp[i+1], dp[i]);
}

console.log(dp[n]);

1. i 일에 상담을 해서 i+t 일에 받을 수 있는 금액을 적고 최대 금액에 표시했다.
2. i 일에 i-1 일 까지 일해서 번 금액의 최대값을 계속 누적했다.
3. 1. 2. 를 합치면 i-1 일 까지 일해서 받을 수 있는 금액의 최대값에 i 일에 일해서 번 금액을 더한 값이 i+t 일에 받을 수 있는 금액보다 클 경우 교체해준다.

"dp 에 저장되는 값은 i-1 일 까지 일해서 받을 수 있는 최대 액수이다." 라는 반복 dp 아이디어만 들어서는 이해가 잘 되지 않아 직접 손으로 전부 풀고 나서야 구현할 수 있었다.