[ Lv 3 ] 거스름돈

풀이 과정

1. DP를 사용하는 문제일 거 같아서 처음에는 현재 금액 기준으로 도달할 수 있는 모든 경우의 수를 계산하였음.
   • dp[i] = dp[i] + dp[i-coin[j]] if (i - coin[j] >= 0)
   • dp[0] = 0
2. 위와 같은 방법으로 하게 되면 중복에 대한 처리가 전혀 되지 않아서 안되는 것 같았음.
   • (1, 2, 2)랑 (2, 1, 1)은 같은 방법
3. 고민하다 다른 사람들의 풀이를 보니 동전별로 dp 적용
   • 동전 단위로 DP 적용
   • dp[i] = dp[i] + dp[coin], 루프를 돌면서 하나의 동전만
4. 위처럼 하면 항상 새로운 방식으로만 개수가 세어짐.
   • 4라고 가정하고, 동전이 (1,2,4)일 때 위 방식으로 한다면..
   • 1, 1, 1, 1
   • 1, 1, 2
   • 2, 2
   • 4

---

소스 코드

    def solution(n, money):
    answer = 0

    dp = [0] * (n+1)
    dp[0] = 1

    for m in money:
        for i in range(1, n+1):
            if i - m >= 0:
                dp[i] += dp[i-m]
            print(dp, m)
    answer = dp[n] % 1000000007

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges