프로그래머스: 거스름돈

문제

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

 

문제 풀이

 거슬러 주어야 하는 돈 N이 있고, 화폐 단위가 주어진다. 이때, 돈을 거슬러 줄 수 있는 방법의 경우의 수를 계산하여 반환하는 문제이다. 이 문제는 이전에 다룬, 백준: 2293 동전 1 문제와 동일한 문제이다. `DP`를 통해 각 경우의 수를 계산하여야 하며, 그렇지 않을 경우 시간 초과가 발생한다.

 

def solution(n, money):
    dp = [1] + [0] * n

    for coin in money:
        for price in range(coin, n + 1):
            if price >= coin:
                dp[price] += dp[price - coin]
    
    return dp[n] % 1000000007