[JS] 동적계획법 with 백준

❗️연속합 - 백준 1912번

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

✅ 동적계획법을 이용한 구현

const N = 10;
const array = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1];

let result = array[0];
let dp = [];
dp[0] = array[0];
for (let i = 1; i < array.length; i++) {
  dp[i] = Math.max(array[i], array[i] + dp[i - 1]);
  result = Math.max(dp[i], result);
}
console.log(result);

❗️RGB거리 - 백준 1149번

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

✅ 동적계획법을 이용한 구현

let dir = __dirname + "/1149.txt";
const path = process.platform === "linux" ? "./dev/stdin" : dir;
const input = require("fs").readFileSync(path).toString().trim().split("\n");

const N = Number(input.shift());
const houses = input.map((el) => el.split(" ").map(Number));

dp = Array.from(Array(N), () => Array(3).fill(Number.MAX_SAFE_INTEGER));
dp[0] = houses[0];
for (let i = 1; i < houses.length; i++) {
  for (let a = 0; a < houses[i].length; a++) {
    for (let b = 0; b < houses[i].length; b++) {
      if (a === b) continue;
      let tmp = houses[i][a] + dp[i - 1][b];
      dp[i][a] = Math.min(dp[i][a], tmp);
    }
  }
}

console.log(Math.min(...dp[N - 1]));

❗️쉬운 계단 수 - 백준 10844번

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

✅ 동적계획법을 이용한 구현

let dir = __dirname + "/10844.txt";
const path = process.platform === "linux" ? "./dev/stdin" : dir;
const input = require("fs").readFileSync(path).toString().trim().split("\n");

const N = Number(input[0]);
// dp[i][0~9] : i 길이의 맨뒷자리가 0~9인 계단 수의 갯수
let dp = Array.from(Array(N + 1), () => Array(10).fill(0));
dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1];
const mod = 1000000000;

for (let i = 2; i <= N; i++) {
  for (let j = 0; j < 10; j++) {
    if (j === 0) dp[i][0] = dp[i - 1][1];
    else if (j === 9) dp[i][9] = dp[i - 1][8];
    else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];

    dp[i][j] %= mod;
  }
}

console.log(dp[N].reduce((acc, cur) => acc + cur) % mod);

❗️❗️❗️ 평범한 배낭 - 백준 12865번 (DP의 대표 문제)

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

✅ 냅색 알고리즘

// i번째까지 물건을 살펴보고 배낭의 용량이 j였을때 배낭에 들어간 물건의 가치합의 최대
dp[i][j]
w[i] // i번째 물건의 무게
v[i] // i번째 물건의 가치
1. j가 현재 물건의 무게 w와 같거나 작은 경우
- i번째 물건을 넣을 수 없음
- 물건을 담지 않았으므로 이전의 값을 복사
dp[i][j] = dp[i-1][j]

2. j가 현재 물건의 무게 w보다 큰 경우
- 물건을 담았을 때와 담지 않았을때의 가치를 비교
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i]] + v[i])

✅ 동적계획법을 이용한 구현

let dir = __dirname + "/12865.txt";
const path = process.platform === "linux" ? "./dev/stdin" : dir;
const input = require("fs").readFileSync(path).toString().trim().split("\n");

const [N, K] = input.shift().split(" ").map(Number);
let lists = input.map((el) => el.split(" ").map(Number));

// i번째 물건까지의 배낭용량 j일때의 가치
const dp = Array.from(Array(N + 1), () => Array(K + 1).fill(0));
for (let i = 1; i <= N; i++) {
  for (let j = 1; j <= K; j++) {
    if (lists[i - 1][0] <= j) {
      dp[i][j] = Math.max(
        dp[i - 1][j],
        dp[i - 1][j - lists[i - 1][0]] + lists[i - 1][1]
      );
    } else {
      dp[i][j] = dp[i - 1][j];
    }
  }
}

console.log(dp[N][K]);