[Level 3] 거스름돈

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

코딩테스트 연습 - 거스름돈

---

접근

다른 사람들의 풀이를 참고하였다.

현재까지 이해한 것은 각각의 money로 만들 수 있는 1부터 n까지의 수를 누적해서 계산해나간다.

1은 1부터 n까지의 돈을 만드는 경우의 수가 1개이다.

2는 1을 만들 수없기 때문에 이전의 1에서 1을 만드는 경우의 수에서 가져온다. 

그리고 2로 2를 만들 수 있는 경우의 수는 1+1과 2이다. 즉 1로 만든 수와 자기 자신을 사용한 결과이기 때문에 이전에 1에서 2로 만든 경우의 수+(2-2) 인덱스에 있는 수를 더한다.

2로 3을 만들 때는 1+1+1과 1+2이다. 역시 1에서 3을 만든 경우의 수와 (3-2) 인덱스에 있는 수를 더한다. 

여기서 괄호 안이 의미하는 것은 지불해야할 거스름돈 - 사용한 돈이다. 

 

좀 더 이해해야할 필요가 있다.

 

구현

def solution(n, money):
    answer = 0
    dp = [[0 for _ in range(n+1)] for _ in range(len(money))]
    dp[0][0] = 1
    for i in range(money[0], n+1, money[0]):
        dp[0][i] = 1
    
    for i in range(1, len(money)):
        for j in range(n+1):
            if j >= money[i]:
                dp[i][j] = (dp[i-1][j]+dp[i][j-money[i]])%1000000007
            else:
                dp[i][j] = dp[i-1][j]
    answer = dp[len(money)-1][n]
    return answer