[JavaScript/DP] 백준 골드 4 : 2624 - 동전 바꿔주기

https://www.acmicpc.net/problem/2624

2624번: 동전 바꿔주기

---

📌 작성한 코드 

// 2624
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 = Number(input.shift());
const M = Number(input.shift());
const coins = input.map((str) => str.split(" ").map(Number));

// dp[i][j] = 동전 i번까지 사용해서 만들 수 있는 j값의 개수

const dp = Array.from({ length: M }, () => new Array(N + 1).fill(0));

for (let i = 0; i < M; i++) {
    const [price, count] = coins[i];
    for (let j = 1; j <= count; j++) {
        dp[i][j * price] += 1;
    }

    for (let k = 1; k <= N; k++) {
        for (let j = 1; j <= count; j++) {
            if (k - j * price >= 0 && i - 1 >= 0) dp[i][k] += dp[i - 1][k - j * price];
        }

        if (i - 1 >= 0) dp[i][k] += dp[i - 1][k];
    }
}

console.log(dp[M - 1][N]);

 

📌 설명 

점화식 : dp[i][j] = 동전 i번까지 사용해서 만들 수 있는 j값의 개수

- 동전마다 사용할 수 있는 최대 개수가 정해져 있는데, 반복을 돌면서 해당 개수를 1개, 2개, ..., n개까지 사용한 결과를 업데이트 한다. 

 

동전 i까지 사용해서 j값을 만들 수 있는 방법의 종류

- 1. i-1 동전까지 사용해서 만든 값에 현재 동전을 더해서 j 값 만들기

- 2. 현재 동전 사용하지 않고 j값을 만든 개수 사용하기

for (let i = 0; i < M; i++) { // 사용할 수 있는 동전 종류의 개수
    const [price, count] = coins[i]; // 동전의 값과 사용 할 수 있는 최대 개수
    for (let j = 1; j <= count; j++) { // 현재 동전만 사용해서 만들 수 있는 값의 개수 증가시키기
        dp[i][j * price] += 1;
    }

    for (let k = 1; k <= N; k++) {
        for (let j = 1; j <= count; j++) {
        	// 현재 동전을 j개 사용해서 k값을 만드는 방법의 개수 == 이전 동전까지 사용했을 때 k값 - 현재 동전 j개의 값  
            if (k - j * price >= 0 && i - 1 >= 0) dp[i][k] += dp[i - 1][k - j * price];
        }
        
        // 현재 동전을 안쓰고 k값을 만드는 방법의 개수 추가하기
        if (i - 1 >= 0) dp[i][k] += dp[i - 1][k];
    }
}

 

✅ 성공

효율적으로 푼 풀이는 아니다