[백준] 14501 - 퇴사 (node.js)

문제

 

코드

let fs = require("fs");
// "/dev/stdin"
// "./text.txt"
const [n, ...arr] = fs.readFileSync("./text.txt").toString().split("\n");
const N = Number(n);
const list = arr.map((v) => v.split(" ").map((v) => +v));

let dp = Array(N + 1).fill(0);

for (let i = 0; i < N; i++) {
  const [period, value] = list[i];
  for (let j = i + period; j < N + 1; j++) {
    if (dp[j] < dp[i] + value) dp[j] = dp[i] + value;
  }
}

console.log(dp[N]);

 

문제 해결 과정

 

1. 완전 탐색

첫날부터 상담을 하는 경우와 안하는 경우를 나눠서 dfs를 한다.

이때 퇴사일이 O(2^N)이라고 생각했고 1 <= N <= 15이므로 2초 안에 충분히 해결할 수 있다고 생각했다.

현재 상담을 하는 경우, 상담을 완료하는 시간이 퇴사일(N)을 넘지 않아야 한다. 퇴사일을 넘지 않는다면 받을 금액을 더한 후, 현재 상담을 마쳤을 때의 일자로 넘어가서 dfs를 반복한다.

만약 현재 상담을 하지 않는 경우라면, 다음날로 넘어간다.

퇴사일에 다다르면 현재까지 더한 금액의 최댓값으로 업데이트한다.

 

2. DP

하지만 완전 탐색이 아닌 dp로 푸는 방법을 생각해보았다. 상담 기간이 오래 걸릴수록 금액을 더 받는 것이 아니므로 조건이 랜덤이였고, 완점 탐색으로도 풀 수 있기 때문에 dp로 풀 수 있는 가능성도 생각해보았다.

DP의 시간 복잡도는 O(N*K)이므로 최악의 경우를 고려했을 때 문제 제한인 2초에 충분했다.

문제 풀이

 

우선 list에 [상담 기간, 비용]을 저장해둔다.

그리고 이중 반복문을 돌게 되는데 i는 i번째 날까지 일했을 때 얻는 최대 수익이다. j는 i번째 날에 상담을 받았을 때 상담이 가능한 모든 날짜이다. 즉, (i번째 날 + 상담기간)부터 마지막날까지를 고려하는 것이다.

반복문을 돌면서 최댓값을 비교하면서 dp 배열을 채워주면 list의 가장 마지막 값을 출력해주면 된다.