[백준] 14501번 퇴사 (JavaScript)

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

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.split(' ').map(Number));
let N = input.shift()[0];
let dp = new Array(N).fill(0);
for (let i = 0; i < N; i++) {
  const [d, p] = input[i];
  if (i + d > N) { // 퇴사 전 처리 할수 없는 일
    continue;
  }
  dp[i] += p; // 상담 진행 했을 경우 얻는 수익 저장

  for (let j = d + i; j < N; j++) {
    dp[j] = Math.max(dp[i], dp[j]); // 해당 날짜의 상담을 진행 했을 경우와 다른 상담을 진행 했을 경우 비교
  }
}
console.log(Math.max(...dp));

 

전형적인 dp 문제이다.

두 번째 for문이 많이 헷갈릴 텐데 나누어 생각을 해보자면 다음과 같다.

1~3일 상담은 총 3일이 걸리므로 2, 3일에는 상담이 불가능하여 dp는 [10, 0, 0, 10, 10, 10, 10]이 된다.

2~6일 상담은 1일에 진행 상담보다 수익이 크므로 dp는 [10, 20, 0, 10, 10, 10, 20]이 된다.

3일 상담은 1~4일에 진행한 수익과 같으므로  dp는 [10, 20, 10, 10, 10, 10, 20]이 된다.

4일 상담은 이미 진행된 수익 + 이번 상담 수익 이므로 30의 수익이며 dp는 [10, 20, 10, 30, 30, 30, 30]이 된다.

5~6일 상담은 이미 진행된 수익 + 이번 상담 수익 이므로 45의 수익이며 dp는 [10, 20, 10, 30, 45, 30, 45]이 된다.

6, 7일 상담은 불가능.