백준 14501 퇴사

문제

제한사항

입출력 예

풀이

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

const solution = (N, counseling) => {
  const dp = new Array(N).fill(0);

  for (let i = 0; i < N; i++) {
    const [cost, profit] = counseling[i];
    if (i + cost > N) continue;
    dp[i] = dp[i] + profit;
    for (let j = i + cost; j < N; j++) {
      dp[j] = Math.max(dp[j], dp[i]);
    }
  }
  return Math.max(...dp);
};

const N = Number(input[0]);
const counseling = input
  .slice(1)
  .map((v) => v.split(' ').map(Number));

console.log(solution(N, counseling));

• 다이나믹 프로그래밍 방식으로 풀어야한다.
• i는 idex이면서도 몇일째 인지를 표현해준다. 그래서 i + cost의 값을 비교하는 조건문을 사용하였다.
• 최대값을 넘어가면 할 수 없는 일이니 다음 요소를 본다.
• 넘어가지 않았다면 dp배열에 값을 누적한다. 그리고 i+cost 인덱스의 dp배열에도 같은 값을 할당해준다.
• 예를 들어 첫째날에 3일 걸리는 일을 했다. 그럼 2~3일에는 다른 일을 못하니 4일째의 dp값도 일단 1일째의 dp값과 같아지는 것이다.(처음엔 0일테니)

복습

const input = ["7", "3 10", "5 20", "1 10", "1 20", "2 15", "4 40", "2 200"];

const sol = (input) => {
  const n = +input.shift();
  const arr = input.map((e) => e.split(" ").map(Number));

  const dp = new Array(n).fill(0);

  for (let i = 0; i < n; i++) {
    const [cost, money] = arr[i];
    if (i + cost > n) continue;
    dp[i] = dp[i] + money;
    for (let j = i + cost; j < n; j++) {
      dp[j] = Math.max(dp[j], dp[i]);
    }
  }
  return Math.max(...dp);
};

console.log(sol(input));