[알고리즘] 프로그래머스 - 거스름돈

프로그래머스 - 거스름돈

백준 - 동전 1과 같은 문제인데 예전에 백준에서는 풀었던 문제인데 이번에 풀지 못했다.

다른 사람 풀이

def solution(n, money):
    MOD = 1000000007
    money.sort()
    dp = [0] * (n+1)
    dp[0] = 1
    for coin in money:
        for price in range(coin, n+1):
            if price >= coin:
                dp[price] += (dp[price - coin])%MOD

    return dp[n] % MOD