https://www.acmicpc.net/problem/9084
9084번: 동전
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는
www.acmicpc.net
📌 작성한 코드
// 9084
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 T = Number(input.shift());
for (let i = 0; i < T; i++) {
const N = Number(input.shift());
const coins = input.shift().split(" ").map(Number);
const target = Number(input.shift());
const dp = new Array(target + 1).fill(0);
for (let j = 0; j < N; j++) {
const coin = coins[j];
dp[coin] += 1;
for (let k = coin; k <= target; k++) {
dp[k] += dp[k - coin];
}
}
console.log(dp[target]);
}
📌 설명
dp[i] = i값을 만들 수 있는 경우의 수
- dp[i] = sum(dp[i-coin[j])) (j는 동전의 번호)
예를 들어 동전이 [1,2,3,4]가 존재하고 구하고자 하는 target 값이 5라고 하자.

백준 2293 -동전1과 같은 문제이다. 해당 문제는 자바스크립트로 풀 수 없었지만 해당 문제는 풀 수 있다.
https://youme016.tistory.com/390
[JavaScript] 백준 골드 5 - 2293 : 동전 1 (solve X)
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연
youme016.tistory.com
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript] 백준 골드 5 : 1174 - 줄어드는 수 (0) | 2024.03.11 |
|---|---|
| [JavaScript/DP] 백준 골드 5 : 2294 - 동전 2 (1) | 2024.03.09 |
| [JavaScript/DP] 백준 골드 5 : 9251 - LCS (0) | 2024.03.07 |
| [JavaScript/DFS] 백준 골드 5 : 1240 - 노드 사이의 거리 (0) | 2024.03.06 |
| [JavaScript/구현] 백준 골드 3 : 14890 - 경사로 (1) | 2024.03.06 |