[백준] 22115 창영이와 커피 - javascript

📌 문제

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

📌 풀이

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

let [n, k] = input[0].split(" ").map(Number);
let coffee = new Array(n);
coffee = input[1].split(" ").map(Number);
let ans = 0;
let dp = new Array(k + 1);
for (let i = 0; i < dp.length; i++) {
  dp[i] = new Array(n + 1).fill(101);
}
for (let i = 0; i < n + 1; i++) {
  dp[0][i] = 0;
}
for (let i = 1; i < k + 1; i++) {
  for (let j = 1; j < n + 1; j++) {
    if (i - coffee[j - 1] < 0) dp[i][j] = dp[i][j - 1];
    else if (!(dp[i - coffee[j - 1]][j - 1] === 101 && dp[i][j - 1] === 101)) {
      dp[i][j] = Math.min(dp[i][j - 1], dp[i - coffee[j - 1]][j - 1] + 1);
    }
  }
}
ans = dp[k][n];
if (ans === 101) {
  console.log(-1);
} else {
  console.log(ans);
}

✔ 알고리즘 : DP

✔ dp[i][j] 는 dp[카페인][커피종류수]로 현재 커피종류수(j)로 카페인(i)을 만들 수 있는 최소한의 커피 종류수라고 설정했다.

✔ 커피의 종류는 최대 100종류이므로 101로 초기화

✔ 카페인이 0인 경우 커피종류수와 상관없이 dp값은 0이다

✔ 현재 인덱스의 커피를 마시는 경우와 안마시는 경우로 나눠서 dp를 계산한다

✔ 마시는 경우 : 현재 커피의 카페인 수치를 뺀 dp값에 +1

✔ 안마시는 경우 : 현재 인덱스 전까지의 커피로 주어진 카페인만들기

✔ 점화식은 아래식으로 작성하면 된다.

 dp[i][j] = Math.min(dp[i][j - 1], dp[i - coffee[j - 1]][j - 1] + 1);

✔ 난이도 : 백준 기준 골드5