1. 문제 설명

거스름돈

2. 문제 풀이

주어진 동전을 사용해 총합이 n이 될 수 있는 경우를 구해야 한다.

1. 0원부터 n원까지 주어진 동전을 통해 총합을 구할 수 있는 경우의 수를 담을 배열 dp
2. 동전은 자신 이상의 금액을 치르는 데 사용할 수 있다.
3. cost-coin을 구하는 데 사용되는 경우가 cost를 구하는 데에도 사용된다.

동전 [1, 2, 5]를 통해 5원을 구하는 경우의 수를 통해 살펴보자.

1. 1원을 꺼낸다. 1원부터 5원까지 금액 중 1원을 지불해 총합을 구할 수 있는 경우를 보자.

   1원	2원	3원	4원	5원
   1	1	1	1	1

2. 2원을 꺼내 확인해보자. 2원 짜리 동전으로는 1원은 당연히 계산할 수 없다.

   1원	2원	3원	4원	5원
   1	1+1	1+1	1+2	1+2

3. 마지막으로 5원을 꺼낸다.

   1원	2원	3원	4원	5원
   1	1+1	1+1	1+2	1+2+1

• dp[0]=1인 까닭은 총합 n원을 n원 동전으로 계산하는 것을 카운트하기 위함이다.

3. 나의 풀이

def solution(n, money):
    money.sort()
    dp = [0]*(n+1)
    dp[0] = 1
    # 한 가지 종류의 coin만 쓸 때 사용 -> 1
    for coin in money:
        for cost in range(coin, n+1):
            dp[cost] += dp[cost-coin]
            # 각 coin 이상 값 -> cost-coin으로도 계산 가능
            # coin이 지불 가능한 최소 형태 (1, 2, 5 등)
    return dp[n]%1000000007