[JS] 백준 2293번 : 동전 1 - DP (백준 메모리초과)

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

2293번: 동전 1

 

 

📋풀이방법

1. 손으로 풀 수 있을 때까지 문제를 나열해보자

2. 이때 규칙을 찾아야한다.

3. 그림을 봤을 때 1원만 사용했을 때와 1원과 2원을 사용했을 때의 차이가 있다.

4. 차이에서 규칙을 찾아야한다.
5. 이때 중요한 점은 0원일 때의 경우의 수도 넣어야한다.

 ->0원을 만드는 경우의 수는 0개의 동전을 선택하는 방법이므로 1가지입니다.

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let [N,K]=input.shift().split(" ").map(Number);
let arr = [];
for (var i = 0; i < N; i++){
    arr.push(Number(input.shift()));
}

let dp = Array.from({ length: K + 1 }, () =>0);
dp[0] = 1;
arr.forEach((coin) => {
    for (var i = coin; i <= K; i++){
        dp[i]+=dp[i-coin]
    }
})
console.log(dp[K])

 

 

💢백준 메모리 초과 이슈

-node.js로 하면 메모리 초과가 뜬다.

-백준 문제에서 메모리를 4MB인 것이 문제라고 한다.

-node.js로는 풀 수없어서 c++로 바꿔 제출 했다.