https://www.acmicpc.net/problem/2294
2294번: 동전 2
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어
www.acmicpc.net
📌 작성한 코드
// 2294
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, K] = input.shift().split(" ").map(Number);
const coins = [...new Set(input.map(Number))];
const dp = Array.from({ length: N + 1 }, () => new Array(K + 1).fill(Infinity));
for (let j = 1; j <= K; j++) {
if (j % coins[0] === 0) dp[1][j] = j / coins[0];
}
for (let i = 2; i <= N; i++) {
const coin = coins[i - 1];
for (let j = 1; j <= K; j++) {
if (j === coin) {
dp[i][j] = 1;
} else if (j - coin >= 1 && j % coin === 0) {
dp[i][j] = Math.min(dp[i][j - coin] + 1, dp[i - 1][j], j / coin);
} else if (j - coin >= 1) {
dp[i][j] = Math.min(dp[i][j - coin] + 1, dp[i - 1][j]);
} else if (j % coin === 0) {
dp[i][j] = Math.min(dp[i - 1][j], j / coin);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
if (dp[N][K] === Infinity) {
console.log(-1);
} else {
console.log(dp[N][K]);
}
// 2번째 풀이
const dp2 = Array(K + 1).fill(Infinity);
dp2[0] = 0;
for (let i = 0; i < N; i++) {
const coin = coins[i];
for (let j = 1; j <= K; j++) {
if (j - coin >= 0) dp2[j] = Math.min(dp2[j - coin] + 1, dp2[j]);
}
}
if (dp2[K] === Infinity) {
console.log(-1);
} else {
console.log(dp2[K]);
}
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript] 백준 골드 5 : 5582 - 공통 부분 문자열 (1) | 2024.03.18 |
|---|---|
| [JavaScript] 백준 골드 5 : 1174 - 줄어드는 수 (0) | 2024.03.11 |
| [JavaScript/DP] 백준 골드 5 : 9084 - 동전 (0) | 2024.03.08 |
| [JavaScript/DP] 백준 골드 5 : 9251 - LCS (0) | 2024.03.07 |
| [JavaScript/DFS] 백준 골드 5 : 1240 - 노드 사이의 거리 (0) | 2024.03.06 |