프로그래머스 lv3 거스름돈

1. 개요

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

2. 풀이

def solution(n, money):
    DB, DB[0] = [0]*(n+1), 1
    
    # 모든 코인마다 다 넣어본다.
    # DB[거스름돈] += DB[거스름돈-동전의가치]
    # 모든 코인들을 시도했을때 DB[-1]이 답이 된다.
    for coin in money:
        for i in range(coin, n+1):
            DB[i] = (DB[i]+DB[i-coin]) % 1000000007
    return DB[-1]