문제 링크

프로그래머스 문제

풀이

알고리즘에서 굉장히 유명한 문제인 배낭 문제 와 유사한 문제 입니다.
dp를 통해서 어떤 시점에서 가질 수 있는 거스름에 대한 정보를 저장합니다.

코드

function solution (n, money){
    let dp = new Array(n+1).fill(0);
    
    dp[0] = 1; //dp[n]은 n을 거슬러 주기 위한 방법이다.
    // dp[0]는 1의 방법을 가지고 있다. 
    
    for(let i=0; i< money.length; i++){
        const curMoney = money[i]
        for(let j=curMoney; j <=n; j++){
            dp[j] +=dp[j-curMoney] // 이 부분을 채우기 위해서 dp[0]는 0을 사용했다.
            console.log("동전 "+ curMoney +" 로 인해서 현재 dp[" + j +"]에 더해지는 값은 " + dp[j-curMoney] +", 그 결과 dp[" + j +"]는 " +dp[j] + "이 된다" )
            
        }
    }
    
    
    return dp[n];
}