[프로그래머스] 거스름돈 (파이썬, javascript)

dp인건 알겠는데 어디서 계산이 틀린 부분이 있는지 한참을 안되다가 다시 해보니까 3분만에 풀림 

이것이 인생

 

1.

거스름돈 1,2,5원 중 1원을 낼 수 있는 것 다 더해주고 

그다음 2원으로 계산되는 것 다 내준다. 

그 다음 5원 순으로 더한다 

배열 말고 그냥 dict을 사용했고 

from collections import defaultdict
def solution(n, money):
    dp=defaultdict(int)   
    dp[0]=1

    for m in money:
        for i in range(m,n+1):
            dp[i]+=dp[i-m]%1000000007
    return dp[n]

 

2. 자바스크립트

 

function solution(n, money) {
    var answer = 0; 
    let dp=new Array(n+1).fill(0);
 
    for(let i=0;i<money.length;i+=1){
        dp[money[i]]+=1;
        for(let j=money[i]+1;j<=n;j+=1){
            dp[j]=(dp[j]+dp[j-money[i]])%1000000007;
        }
    }
    return dp[n];
}