[프로그래머스] / [Level 3] / [Python] 거스름돈

https://school.programmers.co.kr/learn/courses/30/lessons/12907

프로그래머스

---

DP를 이용해서 풀이해야하는 것은 알겠는데 도저히 방법이 생각이 나지 않아 다른 사람 풀이를 참고하였습니다.

 

여기에서 참고하였습니다.

 

def solution(n, money):
    answer = 0
    
    DP = [1] + [0] * (n)
    
    for m in money:
        for i in range(m, n+1):
            if i >= m:
                DP[i] += DP[i - m]
    
    return answer

print(solution(5, [1, 2, 5])) # 4