[백준/BOJ] 14501 퇴사 (JavaScript)

🌱 문제

[백준/BOJ] 14501 퇴사
얼마 전에 본 코딩테스트에서 이 문제랑 거의 똑같은 문제가 나왔다..!
나 퇴사한 거 어떻게 알고 딱 퇴사 문제가 ~
DP로 풀 수 있을 것 같은데 뇌가 안 돌아가서 재귀로 완탐을 시도했다 (터짐 재귈ㅜㅜ)

그래서 DP로 다시 풀어봄 !!

☘️ 풀이

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
const N = parseInt(input[0]);
const plan = [];

for (let i = 1; i < N + 1; i++) {
  plan.push(
    input[i]
      .toString()
      .split(" ")
      .map((v) => Number(v))
  );
}

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

for (let i = 0; i < N; i++) {
  for (let j = i + plan[i][0]; j < N + 1; j++) {
    if (dp[j] < dp[i] + plan[i][1]) {
      dp[j] = dp[i] + plan[i][1];
    }
  }
}

console.log(dp[N]);

1. 1 ~ N일까지 일할 때 각 날짜에 얻을 수 있는 최대 보수를 dp에 저장하기 위해, dp 리스트를 만든다.

2. N일까지 for문으로 돌면서, i번째 날에 일을 할 경우 그 뒤에 가능한 시나리오를 알아야 한다.

3. 따라서 위 시나리오를 구하기 위해, i번째 날에 일을 하면 그 뒤에 일할 수 있는 j일을 구한다 (이때 j의 범위 : i + plan[i][0] ~ N + 1)

   • 이때, i가 0부터 시작하기 때문에 i + plan[i][0]에 -1을 해주지 않아도 됨

4. j일에 일을 하는 시나리오에서 가능한 최대 보수를 dp[j]에 저장한다.

   • i번째 날에 저장된 최대 보수(이전 시나리오들에서 저장된 보수)에 i번째 날에 일할 경우 받는 보수를 더한다.
   • 가장 큰 보수를 dp[j]에 저장

5. dp의 마지막 요소를 출력하면 최대 보수를 얻을 수 있다 !
   
   

🍀 결과

짜자자잔 ~~~!!!!

🐾 소소한 수확

JS에서도 Python에서도 for문을 돌릴 때 범위를 큰 수에서 작은 수로 1씩 증가하도록 하는 경우, 에러가 나지 않고 실행이 아예 되지 않는다 !

for (let i = 10; i < 1; i++) {
  console.log(i);
}
// 실행 X

for i in range(10, 1):
	print(i)
# 실행 X