# 거스름돈

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://pyohamen.gitbook.io/til/algorithm/programmers/undefined-5.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.