https://www.acmicpc.net/problem/15486
15486번: 퇴사 2
첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)
www.acmicpc.net
📌 작성한 코드 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));
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript] 백준 골드 5 - 2293 : 동전 1 (solve X) (1) | 2024.02.28 |
|---|---|
| [JavaScript/DP] 백준 실버 3 : 1904 - 01타일 (1) | 2024.02.28 |
| [JavaScript/DP] 백준 골드 5 : 17070 - 파이프 옮기기 1 (1) | 2024.02.27 |
| [JavaScript/DP] 백준 골드 5 : 2011 - 암호 코드 (1) | 2024.02.26 |
| [JavaScript/DP] 백준 실버 1 : 4883 - 삼각 그래프 (0) | 2024.02.26 |