14501. 퇴사 (node.js)

문제 요약

[boj] 14501. 퇴사 (node.js)

풀이

1. 기본 원칙
   • 도착하는 날짜가 존재함이 확인되어야 이전 값을 더함
2. 코드
   • 재귀함수
     • ndateIdx > N 이면 다음 날짜가 존재하지 않으므로 더하지 않음, sum 리턴
     • ndateIdx == N + 1 이면 바로 다음날이 도착일이므로 sum + arr[k][1] 더해준 값을 리턴
       • for (let i = ndateIdx; i ≤ N; i++) 로 i 값을 다음 날짜로 지정
       • 다음 날짜를 대상으로 재귀함수를 실행
       • 값이 반환되면 최대인지 확인하고 대입해줌
3. 유의할 점
   • 마지막 날에 소요일수가 1인 경우는 N+1 에 마무리되므로 상담이 가능함.

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  const N = Number(input());
  let arr = [];

  for (let i = 1; i <= N; i++) arr[i] = input().split(" ").map(Number);
  let result = 0;
  for (let i = 1; i <= N; i++) {
    let cand = rec(i, 0);
    if (cand) result = Math.max(cand, result);
  }
  console.log(result);

  function rec(k, sum) {
    let ndateIdx = k + arr[k][0];
    if (ndateIdx == N + 1) sum += arr[k][1];
    if (ndateIdx > N) return sum;
    sum += arr[k][1];
    for (let i = ndateIdx; i <= N; i++) {
      let fin = rec(i, sum);
      if (fin) result = Math.max(fin, result);
    }
  }
};

let _line = 0;
const input = () => stdin[_line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});