[백준/G5] 15486 퇴사 2

https://www.acmicpc.net/problem/15486

시간복잡도

dp를 업데이트 하는 for문으로 인해 O(N)

풀이

처음에는 상담일자를 충족한 경우에 먼저 집중(2)해서 dp의 최댓값을 구하는 방식을 시도했는데

매일 수익을 업데이트하는 로직(1)이 필요했고, 이를 통해 dp의 마지막 값을 반환하는 방법으로 바꿔 풀었다

최종코드

// 퇴사일 전까지 상담을 적절히 해서 얻을 수 있는 최대 수익
// 상담에는 소되는 일수(T)와 수익이(P) 주어지는데
// 상담은 한번에 하나씩만 되며, 퇴사하는 날짜까지 상담 일수가 이어지면 안됨

function getMaxBenefit(N, arr) {
  const dp = Array.from({ length: N + 1 }, () => 0);

  for (let i = 0; i < N; i++) {
    let [T, P] = arr[i];
    const days = i + T;

    // (1) 기본적으로 받을 수 있는 최대 수익 매일 업데이트
    dp[i + 1] = Math.max(dp[i + 1], dp[i]);

    // (2) 퇴사 전 기간 안에서만 profit을 반영한 업데이트
    if (days <= N) {
      dp[days] = Math.max(dp[i] + P, dp[days]);
    }
  }
  return dp[N];
}

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./15486.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = parseInt(input[0]);
const arr = input.slice(1).map((num) => num.split(" ").map(Number));

let answer = getMaxBenefit(N, arr);

console.log(answer);

'이 문제'라서 핵심이 되는 부분은 빨리 구현했지만 기본적인 dp의 업데이트 측면에서 좀 부족했던 면이 있었던 듯 하다.

281904kb 2272ms