Programmers - 거스름돈

문제 링크

이전에 비슷한 dp문제를 푼 기억이 있어서 쉽게 풀었다.

d[i][j] = 0~i번째 화폐를 사용해서 j원을 만드는 방법의 갯수
d[i][j] = d[i-1][j] (i번째 화폐 없이 j원 만드는 방법) +
d[i]j-money[i]] (j-money[i]원을 만드는 각각의 방법에 i번째 화폐 1개를 더하는 방법)

def solution(n, money):
    MOD = 1000000007
    d = [[0 for _ in range(n+1)] for __ in range(len(money))]
    money.sort()

    # 첫 번째 화폐만을 이용하는 경우
    for j in range(1, n+1):
        if j % money[0] == 0:
            d[0][j] = 1

    for i in range(1, len(money)):
        m = money[i]
        d[i][m] += 1
        for j in range(1, n+1):
            d[i][j] += d[i-1][j]
            if j-m >= 0:
                d[i][j] += d[i][j-m]
            d[i][j] %= MOD

    return d[len(money)-1][n]