문제 개요

문제: 동전 2

분류: DP

난이도: 골드5

문제 풀이

DP를 활용해 풀 수 있다.

dp 배열에서 각 동전의 가치에 해당하는 부분을 1, 나머지를 Infinity로 초기화한다.
그리고 모든 동전에 대해 해당 동전을 사용했을 때 동전의 가치 v에서부터 k까지, 각 값을 만들기 위해 필요한 최소 동전 개수를 구한다.

현재 만들려는 값이 i라고 할 때, dp 배열은 아래와 같이 채울 수 있다.

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

dp[i-v]+1인 이유는 i-v을 만들기 위해 사용한 최소 동전의 개수에서 현재 동전을 1개 더 사용하면 i를 만들 수 있기 때문이다.

코드

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

const [n, k] = nk.split(" ").map(Number);
value = value.map(Number).sort((a, b) => a - b);

const dp = new Array(k + 1).fill(Infinity);

value.forEach((v) => {
  dp[v] = 1;
  for (let i = v; i <= k; i++) {
    dp[i] = Math.min(dp[i], dp[i - v] + 1);
  }
});

dp[k] === Infinity ? console.log(-1) : console.log(dp[k]);