[JavaScript/DP] 백준 골드 5 : 15486 - 퇴사 2

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

15486번: 퇴사 2

---

📌 작성한 코드 1 (697956KB, 4392ms)

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

const N = Number(input.shift());
const list = input.map((str) => str.split(" ").map(Number));

const ends = Array.from({ length: N + 1 }, () => []);
list.forEach(([t, p], i) => {
    if (i + t >= N + 1) return;
    ends[i + t].push([t, p]);
});

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

for (let i = 1; i <= N; i++) {
    const temp = [];
    ends[i].forEach(([t, p]) => {
        temp.push(dp[i - t] + p);
    });
    dp[i] = Math.max(...temp, dp[i - 1]);
}

console.log(dp[N]);

📌 설명 1

가장 먼저 풀었던 방법으로, 비용을 받는 날짜를 기준으로 비용과 기간을 저장하여 dp를 구현하였다.

반복문을 돌며 현재 나온 인덱스가 i이면, i+t의 날에 p의 금액을 받게 되니까 ends[i+t]에 p를 저장해주었다.

const ends = Array.from({ length: N + 1 }, () => []);
list.forEach(([t, p], i) => {
    if (i + t >= N + 1) return; // 범위를 벗어나면 제외
    ends[i + t].push([t, p]);
});

점화식 : dp[i] = i번째 날 일 때 비용의 최대 값 = Math.max(dp[i-1], ... i 날에 추가되는 비용을 계산한 경우의 값들)

- dp[i-1]은 아무런 일이 추가되지 않아도 전날의 비용을 그대로 받을 수 있기 때문에 추가해줘야 한다.

- dp[i-t] + p는 현재에서 t일 전의 비용 최댓값에 비용 p를 더한 값이다. 

 

문제는 풀렸지만 너무 많은 시간,공간 복잡도가 사용되어서 다른 방법을 찾아보게 되었다.

 

---

📌 작성한 코드 2 (693312KB, 4064ms)

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

const N = Number(input.shift());
const list = input.map((str) => str.split(" ").map(Number));

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

for (let i = 1; i <= N; i++) {
    const today = i;
    const [time, pay] = list[i - 1];

    if (today + time <= N + 1) {
        dp[today + time] = Math.max(dp[today + time], dp[today] + pay);
    }
    dp[today + 1] = Math.max(dp[today + 1], dp[today])
}

console.log(dp[N + 1]);

📌 설명 2

비용을 받는 날 기준으로 정리해서 사용하지 않고, 현재 기준으로 t날 이후에 p의 금액을 dp에 더하는 방식으로 구현하였다.

1번 문제와 거의 똑같은데 그래도 정리하는 부분이 없으니 더 적게 걸리지 않을까 했지만 거의 비슷한 시간 공간 복잡도가 나와서 아쉬웠다. 그래도 2번 코드가 훨씬 가독성이 좋다고 생각한다,

---

📌 작성한 코드 3 (218940KB, 1764ms)

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

const N = Number(input[0]);
const dp = new Array(N + 1).fill(0);

let max = 0;
for (let i = 0; i < N; i++) {
    const [time, pay] = input[i + 1].split(" ").map(Number);
    if (max < dp[i]) max = dp[i];
    if (i + time > N) continue;
    if (dp[i + time] < max + pay) dp[i + time] = max + pay;
}

console.log(Math.max(...dp));

✅ 성공