거스름돈

• 많은 교과서의 2차원 DP 챕터에서 연습문제로 자주 보이는 유명한 문제이다.

• dp[m][n]을 money[0]부터 money[m]까지의 화폐를 가지고 n원을 만들 수 있는 방법의 수라고 하자.
• 이 것을, money[m] 없이 n원을 만드는 방법과 money[m]을 포함해서 만드는 방법으로 나누어 생각하자
  • money[m]없이 n원을 만드는 방법은 dp[m-1][n]과 같다
  • money[m]을 한번 이상 포함해서 n원을 만드는 방법은, 어떤식으로 n-money[m] 원을 만들고 마지막으로 money[m]짜리 화폐를 한번 사용한다고 생각하면 된다. 즉, dp[m][n-money[m]]이다
• 종합하면 dp[m][n] = dp[m-1][n] + dp[m][n-money[m]] 이고, O(NM)에 풀리게 된다.
• 공간복잡도 측면에서는 N*M 테이블을 전부 만들 필요가 없다. dp[m][…] 를 계산하기 위해서는 dp[m-1][…] 만 필요하고 dp[m-2]..이하의 행은 필요가 없다. 따라서 두개의 행만 유지하면 된다. 따라서 공간복잡도는 O(NM)이 아니라 O(N)이다.
  • 그리고, 실제로 이 문제에서는 두 개의 행도 필요 없고, 하나의 행만 유지하면서 갱신해나갈수 있다.

"""Solution code for "Programmers 12907. 거스름돈".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/12907
- Solution link: http://www.teferi.net/ps/problems/programmers/12907
"""

MOD = 1_000_000_007


def solution(n, money):
    dp = [1] + [0] * n
    for cur_money in money:
        for i in range(cur_money, n + 1):
            dp[i] = (dp[i] + dp[i - cur_money]) % MOD

    return dp[n]