[2294번: 동전 2 (acmicpc.net)]

풀이

DP 알고리즘을 사용해서 현재의 값을 만들 수 있는 경우의 수가 몇개인지 세보면 될 것 같다.
예를들어서 5원을 만드는 방법은
1+1+1+1+1 = 5
3+1+1 = 5
5 = 5
등등 동전의 종류의 따라 다양한 경우의 수가 나온다.
그 수 중 최소갯수가 답이 되기 때문에 비교해서 최솟값을 기록하면 될 것 같다

코드

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

input = input.map(Number);
const [n, k] = t.split(" ").map(Number);
const dy = Array.from({ length: k + 1 }, () => 10001);

for (let x of input) {
  dy[x] = 1;
}

for (let i = 1; i <= k; i++) {
  for (let x of input) {
    if (dy[i - x]) dy[i] = Math.min(dy[i], dy[i - x] + 1);
  }
}

dy[k] === 10001 ? console.log(-1) : console.log(dy[k]);