[JavaScript] 백준 골드 5 - 2293 : 동전 1 (solve X)

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

2293번: 동전 1

---

📌 작성한 코드 

// 2293
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 = input.map(Number);

// 1번 풀이 (2차원 dp)
const dp = Array.from({ length: N + 1 }, () => Array(K + 1).fill(0));

for (let i = 1; i <= N; i++) {
    const coin = coins[i - 1];
    for (let j = 1; j <= K; j++) {
        if (i === 1) {
            if (j % coin === 0) dp[i][j] += 1;
        } else {
            dp[i][j] += dp[i - 1][j];
            if (j - coin >= 0) {
                dp[i][j] += dp[i][j - coin] || 1;
            }
        }
    }
}

console.log(dp[N][K]);

// 2번 풀이 (1차원 dp)
const dp1 = Array(K + 1).fill(0);
dp1[0] = 1;

for (let i = 0; i < N; i++) {
    const coin = coins[i];
    for (let j = coin; j <= K; j++) {
        if (j - coin >= 0) dp1[j] += dp1[j - coin];
    }
}

console.log(dp1[K]);

 

📌 설명 

푼게 아까워서 올리는 풀이.. 

메모리 제한이 4MB인데 그정도 메모리에서 node.js는 아예 실행조차 안된다고 한다. 한마디로 node.js(js)에서 못푸는 문제이다.

dp 연습할 겸 푼게 아까워서 그래도 풀이 올려본다. 

 

1번 풀이

dp[i][j] : i번째 동전까지 사용했을 때, j금액을 만들 수 있는 경우의 수 

- dp[i][j]에서 고려할 수 있는 부분은 두 가지가 존재한다.

- (1) 현재 동전을 사용하지 않고 j값을 만드는 경우의 수  

- (2) (j - 현재 동전)에서 만들 수 있는 경우의 수 (해당 경우에서 현재 동전을 더하면 j 값을 만들 수 있기 때문에 고려) 

 

2번 풀이 

1번 풀이에서 (1)을 보면 j값이 같은 경우가 계속 해서 더해지면서 중첩되는 것을 확인할 수 있다. 그러므로 이차원 배열로 따로 저장하지 않고, 일차원 dp를 사용하고 같은 j를 가지는 경우는 더해서 보관하는 방식을 사용한다. 

 

✅ 성공

성공하지 못함

https://www.acmicpc.net/board/view/109917

글 읽기 - node.js 제출 시 메모리 관련 오류가 있습니다