Written by 최태열
on 

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

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

코드

def solution(n, money):
    dp=[[0]*(n+1) for _ in range(len(money))]
    
    dp[0][0]=1
    for i in range(money[0],n+1,money[0]):
        dp[0][i]=1
    
    for x in range(1,len(money)):
        for y in range(n+1):
            dp[x][y]=dp[x-1][y]+dp[x][y-money[x]] if y>=money[x] else dp[x-1][y]
    
    return dp[-1][-1]%1000000007

dp로 풀었다.

어느 돈을 맞출 때, 마지막 화폐가 무엇인지를 고려하여

거스름돈에 해당하는 길이의 배열을 화폐의 종류만큼 선언했다.

초기값으로 가장 적은 단위의 화폐로 나누어 떨어지는 금액을 1로 만들었다.

적은 금액부터 일정 개수로 적용한다고 생각하면 중복을 막을 수 있다.

따라서 dp[x][y]=dp[x-1][y]+dp[x][y-money[x]]가 된다.

Discussion and feedback