[JavaScript] 백준 2294 동전 2 (JS)

동전 2

📚 문제 설명

---

N개의 동전을 이용해 K원을 만들려고 한다.
N개의 동전의 가치가 주어졌을 때,
동전의 갯수를 최소로 사용하여 K원을 만드는 경우 몇개인가?

👨🏻‍💻 풀이 과정

---

기본적인 사고 과정은 0부터 K까지 각각의 경우의 최소 경우를 저장하는 것이다.

그 후 각각의 동전이 있을 경우 갯수를 새롭게 갱신하면 된다.

예를들어 N = 3, K = 3 이고 동전의 가치가 [1, 2, 3]일 경우 아래와 같이 된다.

	0	1	2	3
동전 수	0	Number.MAX_SAFE_INTEGER	Number.MAX_SAFE_INTEGER	Number.MAX_SAFE_INTEGER

가치가 1일 떄,
(i - 1)원 일때의 동전 수 + 1과 기존의 값인 i를 비교하여 더 작은 값으로 변경.

	0원	1원	2원	3원
동전 수	0	1	2	3

가치가 2일 떄,
(i - 2)원 일때의 동전 수 + 1과 기존의 값인 i를 비교하여 더 작은 값으로 변경.

	0원	1원	2원	3원
동전 수	0	1	1	2

가치가 3일 떄,
(i - 3)원 일때의 동전 수 + 1과 기존의 값인 i를 비교하여 더 작은 값으로 변경.

	0원	1원	2원	3원
동전 수	0	1	1	1

마지막으로 만약 해당 동전의 경우의 수가 초기값과 같으면 불가능하다는 뜻이기 때문에 -1을 리턴하면 된다.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let [N, K] = input.shift().split(' ').map(Number);
    let Coins = input.map(Number);

    let dp = new Array(K + 1).fill(Number.MAX_SAFE_INTEGER);
    dp[0] = 0;

    for (let i = 0; i < Coins.length; i++) {
        for (let j = Coins[i]; j < dp.length; j++) {
            dp[j] = Math.min(dp[j - Coins[i]] + 1, dp[j]);
        }
    }
	// 불가능할 경우 -1을 리턴.
    console.log(dp[K] === Number.MAX_SAFE_INTEGER ? -1 : dp[K]);

!https://velog.velcdn.com/images/dannysir/post/252a7b63-1c6c-4b86-b0d4-788d8489be7b/image.png

🧐 후기

---

동전 1 문제와 유사한 사고로 진행을 했는데 무사히 잘 풀 수 있었다.
동전 1 문제의 경우 메모리 제한 때문에 JavaScript로 통과를 할 수 없었는데 다행히 이 문제는 메모리 제한이 여유로워서 통과할 수 있었다.