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

프로그래머스_거스름돈

거스름돈 문제인데 화폐가 각각의 배수가 되지 않는다면, dp로 풀어야한다
목표 금액이 j원이고 현재 화폐가 i원이라면,
j원을 만드는 경우의 수 = (j-i)원을 만드는 경우의 수 + 뒤에 i원을 붙이는 것
이기 때문에 dp[j] += dp[jp-i]라고 작성을 해준다
또한, 현재 화폐 i원은 목표 금액이 i원보다 작은 금액대를 만드는 데에는 영향을 끼치지 않으므로 j의 범위를 (i+1,n+1)까지만 목표 금액 범위를 설정해준다

def solution(n, money):
    dp = [0]*(n+1)
    for i in money:
        dp[i] += 1
        for j in range(i+1,n+1):
            dp[j] += dp[j-i]
        
    answer = dp[n]%(int(1e9)+7)
    return answer