[백준] 14501번: 퇴사 - Node.js (자바스크립트)

1. 문제 ㅡ 14501번: 퇴사 (난이도: Silver III)

14501번: 퇴사

2. 풀이 ㅡ Node.js (자바스크립트)

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input.shift();
const payChart = input.map(info => info.split(' ').map(val => +val));

const getMaxPay = () => {
  let max = -Infinity;

  const dfs = (idx, total) => {
    max = Math.max(max, total);

    for (let i = idx; i < N; i++) {
      const [time, pay] = payChart[i];
      const nextWorkDay = i + time;

      dfs(nextWorkDay, nextWorkDay > N ? total : total + pay);
    }

    return max;
  };

  return dfs(0, 0);
};

console.log(getMaxPay());

2-1. 풀이 설명

브레이크 포인트를 잡기 어려웠던 문제였다. 다행이도 N이 0과 15 사이의 정수였기 때문에 따로 브레이크 포인트를 잡지 않고 그냥 N만큼 탐색해도 쉽게 풀린다. 대신 nextWorkDay가 유효하지 않은 경우, 즉 백준이가 다음으로 일 할 수 없는 날인 경우에는 누적된 금액에 pay를 더하지 않고 탐색을 하도록 했다. 따라서 백준이가 일 할 수 없는 날부터는 max 액수가 갱신되지 않는다.