거스름돈

https://programmers.co.kr/learn/courses/30/lessons/12907

• dp 를 만들어가는 과정을 2중 포문으로 하는 것,

  • 쌓아간다는 것에 집중하자. 화폐 단위 하나하나씩 dp 를 쌓아가자.

  • 화폐가 추가 됨으로써 기존의 DP 에 방법이 하나씩 추가 된다.

  • 다시 한 번 정말 중요한건, 화페 단위 하나씩 전부 DP 를 처음부터 끝까지 해야 한다는 것

• 우선 화폐가 맨 앞에 있는 것만 있다고 가정을 하고 dp 를 쫙 만들어준다.

  • 이 결과에 주목하자. 현재 화폐의 배수들이 초깃값으로 모두 1이 된다.

  • 여기서 초깃값으로 dp[0] 만 1로 해주자.

• 그 후, 다음 화폐가 새로 생김으로써, 이전의 DP 에 새로 생긴 화폐가 생김으로써 경우의 수가 늘어난다.

  • 이전의 DP 와 비교해 갱신을 해나가는 것인데, 여기서 비교대상이 무엇인가 ! 바로 DP 에서 딱 현재 화폐 단위 만큼 빼준 DP 와 비교하는 것이다.

def solution(n, money):

    dp = [1] + [0] * n

    for coin in money:
        for price in range(coin, n + 1):
            dp[price] += dp[price - coin]

    return dp[n] % 1000000007