백준 js 9084번
<문제>
https://www.acmicpc.net/problem/9084
<문제 핵심>
1. 동적 계획법을 사용하여 적은 금액의 동전 값을 시작으로 목표 금액 M원을 만들 수 있는 경우의 수를 메모이제이션 배열에 누적시키며 최종 개수를 구하는 문제였다.
규칙을 파악하는데 이해가 잘 가지 않아서 오랜 시간을 투자했다.. 아직 dp를 잘할려면 멀었나보다
2. 1원, 5원, 10원, 50원, 100원, 500원의 갯수가 주어지고 m원을 만들 수 있는 경우의 수를 구해야한다. 일단 0원을 만들 수 있는 경우의 수는 아무것도 안 사용하는 경우이므로 dp[0] = 1로 설정한다.
dp[2]는 2원짜리를 만들 수 있는 경우의 수를 의미하는데 해당 경우는 1원짜리 2개로 만들 수 있는 경우 1가지만 있다. 즉 이를 통해 점화식을 유추할 수 있는데 앞에서 구한 dp[0] = 1을 이용한다.
function countWaysToMakeChange(coins, m) {
let dp = new Array(m + 1).fill(0);
dp[0] = 1;
for (let coin of coins) {
for (let j = coin; j <= m; j++) {
dp[j] += dp[j - coin];
}
}
return dp[m]; //m까지의 누적합
}
3. 이해하는데 오랜 시간을 투자했고 이해한 내용을 바탕으로 첫번째 테스트케이스의 경우를 정리하고자 한다.
동전의 종류: 1원, 2원
만들어야 하는 금액: 1000원
✅ 1원을 사용한다 가정할 경우 j원을 만들기 위해 사용되는 1원짜리 동전의 갯수는 j개가 사용된다. 1000원을 만들어야 하는 경우도 1원짜리 1000개를 사용해야 하는 경우 1가지가 있으므로 모든 dp 배열은 1로 구성된다.(이전에 구해진 1들은 반복문을 통해서 구해짐)
dp[1000] += dp[1000 - 1] = dp[1000] += dp[999] = 0 + 1 = 1
dp = [1, 1, 1, ..., 1] // dp[1000]까지 모든 값이 1
✅ 2원을 사용한다 가정할 경우 케이스는 2가지가 있다. 1원짜리 2개를 사용하는 경우, 2원짜리 1개를 사용하는 경우가 존재하는데 전자의 경우는 이미 1원을 사용한다고 가정했을 때 구해졌을 것이다. 즉 이거를 식으로 나타내면 다음과 같다.
dp[2] = dp[2] + dp[2-2] = 2
dp[2]는 1원을 2개 사용한 경우이므로 1을 의미하고(이전에 dp[2]는 1로 갱신되어있음) dp[0]의 초기값은 1이다(아무것도 사용하지 않는 경우). 그러므로 총 dp[2]는 2가 나오는데 이는 2원짜리 동전을 1개 사용한 경우도 포함한 것 임을 알 수 있다.
<문제 풀이과정 및 순서도>
1. 입력받은 뒤 입력받은 걸 바탕으로 m원을 만족할 수 있는 경우의 수를 구하는 함수를 호출한다
✅ 다음 테스트케이스로 이동 시에는 3씩 움직인다
const input = require("fs")
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
.toString()
.trim()
.split("\n");
function solve(input) {
const T = +input[0]; //3
let index = 1;
const result = [];
for (let i = 0; i < T; i++) {
const n = +input[index];
const coins = input[index + 1].split(" ").map(Number);
const m = +input[index + 2];
result.push(countWaysToMakeChange(coins, m));
index += 3;
}
console.log(result.join("\n"));
}
solve(input);
2. 주어진 동전으로 만들 수 있는 모든 금액을 계산하는 로직을 구현하고 점화식을 유추한다
function countWaysToMakeChange(coins, m) {
let dp = new Array(m + 1).fill(0);
dp[0] = 1;
for (let coin of coins) {
for (let j = coin; j <= m; j++) {
dp[j] += dp[j - coin];
}
}
return dp[m]; //m까지의 누적합
}
<전체 풀이>
const input = require("fs")
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
.toString()
.trim()
.split("\n");
function countWaysToMakeChange(coins, m) {
let dp = new Array(m + 1).fill(0);
dp[0] = 1;
for (let coin of coins) {
for (let j = coin; j <= m; j++) {
dp[j] += dp[j - coin];
}
}
return dp[m]; //m까지의 누적합
}
function solve(input) {
const T = +input[0]; //3
let index = 1;
const result = [];
for (let i = 0; i < T; i++) {
const n = +input[index];
const coins = input[index + 1].split(" ").map(Number);
const m = +input[index + 2];
result.push(countWaysToMakeChange(coins, m));
index += 3;
}
console.log(result.join("\n"));
}
solve(input);