[baekjoon] 퇴사 14501

14501번: 퇴사 (acmicpc.net)

14501번: 퇴사

---

알고리즘 : 브루트포스, DP

 

재귀함수를 활용하는 부분에서 내용이 꼬여버렸다...

DP를 활용하면 조금 더 쉽게 풀 수 있다고 하는데 DP에 대한 개념이 없어 아직 이해가 안된다.

 

해당 문제를 완전탐색으로 다시한번 풀어보고 DP에 대한 개념이 잡히면 DP를 활용해 다시 한번 풀어보겠다.

 

/**
 * 제출용. 아래 로컬용을 지우고 제출하자.
 */
//  let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
/**
 * 로컬용, 예제.txt를 생성해서 예제를 복붙하자.
 */

function solution() {
  let input = require("fs")
    .readFileSync("input.txt") //"/dev/stdin"
    .toString()
    .trim()
    .split("\n")
    .map((val) => val.trim());
  input;
  console.log(input);
  let n = +input.splice(0, 1)[0];
  let max = -999;
  let schedule = [];
  for (let i = 0; i < n; i++) {
    schedule.push(input[i].split(" ").map((v) => +v));
  }

  console.log(schedule);

  // check
  for (let i = 0; i < n; i++) {
    if (i + schedule[i][0] >= n) {
      continue;
    }
    ans = solve(n, schedule, i, 0, max);
  }

  console.log(ans);
}

function solve(n, schedule, day, sum, max) {
  let nextDay = day + schedule[day][0];

  if (day === n - 1 || nextDay >= n) {
    max = Math.max(max, sum);
    return max;
  } else {
    for (let i = nextDay; i < n; i++) {
      if (i + schedule[i][0] < n) {
        solve(i, sum + schedule[i][1]);
      }
    }
  }
  max = Math.max(max, sum);
}

solution();