[Node.js] 14501_퇴사

문제 설명

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

문제 풀이 방법

이 문제는 DP를 이용한 풀이와 DFS를 이용한 재귀 함수로의 풀이가 가능한 문제이다.

처음 이 문제를 봤을 때는 조합을 이용해 최대로 받을 수 있는 급여를 뽑아낸다 였지만, 
이 문제에서 원하는 것은 근무일 수 혹은 상담 시간의 조합이 아니라 받을 총 급여의 최대값이라 DP를 이용해 풀었다.

 

나는 DP를 이용해 풀이를 진행해보았다.

 

최근 풀었던 가장 긴 바이토닉 부분 수열 문제에서 아이디어를 얻었다. 스케줄을 순회하며 급여를 체크하는 방향으로 설계했다.

 

이 문제에서는 주어진 스케줄의 역순으로 순회하며 값을 구했다.문제에서 처음 상담을 시작한 날짜에 따라 받게되는 급여의 최대값이 달라지기 때문이다.

 

정답 코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n')

const N = +input.shift();
let arr = input.map(e => e.split(' ').map(Number));
let dp = new Array(N).fill(0);

for (let day = 0; day < N; day++){
  const [due, pay] = arr[N - day - 1];
  if (N + 1 >= N - day + due) {
    dp[day] = pay;
    for (let i = 0; i <= day - due; i++){
      dp[day] = Math.max(dp[day], dp[i] + pay)
    }
  }
}

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