백준 2293: 동전 1 - javascript(dp)

문제 출처 

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

 

정답 풀이 

알아보니, 이 문제는 js언어로 메모리 초과가 나는 문제인 것 같다. 

 

이 분의 풀이를 보면 이해가 더 쉬울 것 같다. 

https://www.youtube.com/watch?v=LBOQikSpfNg

 

정답 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [n,k] = input.shift().split(' ').map(v => +v); 
const arr = []; 
for(let i=0; i<n; i++){
    arr.push(Number(input[i]))
}

function solution(n,k,arr){
   const dp = new Array(k+1).fill(0)
    dp[0] = 1 
    for(let i=0; i<n; i++){
        for(let j=arr[i]; j<k+1; j++){
            dp[j] = dp[j] + dp[j-arr[i]]]
        }
        return dp[k]
    }


console.log(solution(n,k,arr))

틀린 코드 

완전탐색의 방법밖에 떠오르지 않았다.. 

메모리 초과... 가 될 걸 알았지만 작성한 이유는, 

요즘에는 코드를 마지막까지 다 작성하는 연습을 하는 중이기 때문임 ! 

function solution(n,k,arr){
    let answer = 0; 
    function dfs(L, sum){
        if(L === n){
           if(sum === k){
               answer++ 
           }
            return; 
     }else{
         let max = parseInt(k/arr[L])
         console.log(L, max)
         for(let i=0; i<=max; i++){
                 dfs(L+1, sum + arr[L] * i)
             }
         }
    }
    dfs(0, 0)
    return answer; 
}