[프로그래머스] 거스름돈 (Python)

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

코딩테스트 연습 - 거스름돈

완전 탐색으로 할 때 너무 오랜 시간이 걸려서 dp인 것은 알았으나 알고리즘을 생각을 못했다.

 

def solution(n, money):
    dp = [1] + [0]*n
    for coin in money:
        for i in range(1,n+1):
            if coin <= i:
                dp[i] = dp[i] + dp[i-coin]
    return dp[n]