> For the complete documentation index, see [llms.txt](https://pyohamen.gitbook.io/til/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://pyohamen.gitbook.io/til/algorithm/programmers/undefined-5.md).

# 거스름돈

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

* dp 를 만들어가는 과정을 2중 포문으로 하는 것,
  * 쌓아간다는 것에 집중하자. 화폐 단위 하나하나씩 dp 를 쌓아가자.
  * 화폐가 추가 됨으로써 기존의 DP 에 방법이 하나씩 추가 된다.
  * 다시 한 번 정말 중요한건, 화페 단위 하나씩 전부 DP 를 처음부터 끝까지 해야 한다는 것
* 우선 화폐가 맨 앞에 있는 것만 있다고 가정을 하고 dp 를 쫙 만들어준다.
  * 이 결과에 주목하자. 현재 화폐의 배수들이 초깃값으로 모두 1이 된다.
  * 여기서 초깃값으로 dp\[0] 만 1로 해주자.
* 그 후, 다음 화폐가 새로 생김으로써, 이전의 DP 에 새로 생긴 화폐가 생김으로써 경우의 수가 늘어난다.
  * 이전의 DP 와 비교해 갱신을 해나가는 것인데, 여기서 비교대상이 무엇인가 ! 바로 DP 에서 딱 현재 화폐 단위 만큼 빼준 DP 와 비교하는 것이다.

```python
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
```
