거스름돈

거스름돈
연습문제
925명 완료

동적계획법,
테이블 작성하는 게 쉽지 않다. 

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

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

만들 금액 ->	0원	1원	2원	3원	4원	5원
1원 동전 경우의 수 ->	1 가지	1	1	1	1	1
2원 동전 추가시 경우의 수 ->	1	1	2	2	3	3
5원 동전 추가시 경우의 수 ->	1	1	2	2	3	4

0원이 가능한 조합은 동전 0개를 사용할 수 밖에 없음 그래서 경우의 수는 1. 
(수학적으로 이렇게 표현하는 게 맞는 지 모르겠지만 여기서는 맞음)

1원 동전으로 n원을 만들 수 있는 경우는 '(1원) * n = n원' 밖에 없으므로 모두 1.

3원을 만드는 경우
1원 동전. '1원+1원+1원'. 경우의 수 1
2원 동전 추가 시, '1원 + 2원' 경우가 추가되므로 2.
5원 동전, 3원의 경우 추가되는 경우는 없으니 2.

4원을 만드는 경우 
1원 동전 4개, 경우 1
2원 동전을 사용하면 1원의 경우에 '1+1+2', '2+2' 추가됨. 3
5원 동전 추가되는 경우가 없음. 

이제 점화식을 찾아보자.. 

2원 동전을 기준으로 생각해 보자. 

3원을 만들 때 2원 동전을 투입하고 경우의 수가 1 늘어났다.
(2+1)원 동전의 경우가 추가 된 것이다. 
늘어난 경우에서 2원 동전을 빼면
늘어난 경우의 수는 1원을 만들 때 2원 동전의 경우와 같다. 

말이 너무 어렵다. 그림을 참고...

5원 동전에서도 체크. 

def solution(n, money):
    table = [([1] + [0] * n) for _ in range(len(money))]  # 0원을 만들 때 경우의 수는 모두 1
    for i in range(money[0], n + 1, money[0]):
        table[0][i] = 1
    for y in range(1, len(money)):
        for x in range(1, n + 1):
            table[y][x] = (table[y - 1][x] + (table[y][x - money[y]] if x - money[y] >= 0 else 0)) % 1000000007
    return table[len(money)-1][n]

정확성  테스트
테스트 1 〉	통과 (14.68ms, 11MB)
테스트 2 〉	통과 (8.23ms, 10.9MB)
테스트 3 〉	통과 (5.15ms, 10.9MB)
테스트 4 〉	통과 (7.08ms, 10.9MB)
테스트 5 〉	통과 (5.60ms, 10.9MB)
테스트 6 〉	통과 (3.27ms, 10.9MB)
테스트 7 〉	통과 (10.99ms, 11.1MB)
테스트 8 〉	통과 (13.92ms, 11.1MB)
테스트 9 〉	통과 (12.88ms, 11.1MB)
테스트 10 〉	통과 (3.48ms, 10.9MB)
테스트 11 〉	통과 (11.70ms, 10.9MB)
테스트 12 〉	통과 (9.06ms, 10.9MB)
테스트 13 〉	통과 (3.11ms, 10.8MB)
테스트 14 〉	통과 (14.04ms, 11.1MB)
효율성  테스트
테스트 1 〉	통과 (1031.33ms, 74.2MB)
테스트 2 〉	통과 (1452.78ms, 185MB)
테스트 3 〉	통과 (1018.44ms, 97.3MB)
테스트 4 〉	통과 (1048.80ms, 89.4MB)
테스트 5 〉	통과 (1921.94ms, 269MB)
테스트 6 〉	통과 (1464.90ms, 142MB)

반복된 mod 연산이 효율성을 떨어트리는 것 같아서.. 

def solution(n, money):
    table = [([1] + [0] * n) for _ in range(len(money))]
    for i in range(money[0], n + 1, money[0]):
        table[0][i] = 1
    for y in range(1, len(money)):
        for x in range(1, n + 1):
            table[y][x] = (table[y - 1][x] + table[y][x - money[y]]) % 1000000007 if x - money[y] >= 0 else table[y - 1][x]
    return table[len(money)-1][n]

정확성  테스트
테스트 1 〉	통과 (12.98ms, 11.1MB)
테스트 2 〉	통과 (7.21ms, 10.9MB)
테스트 3 〉	통과 (4.48ms, 10.9MB)
테스트 4 〉	통과 (6.20ms, 10.9MB)
테스트 5 〉	통과 (4.83ms, 10.9MB)
테스트 6 〉	통과 (2.88ms, 10.9MB)
테스트 7 〉	통과 (9.67ms, 11MB)
테스트 8 〉	통과 (12.23ms, 11.1MB)
테스트 9 〉	통과 (11.34ms, 11.1MB)
테스트 10 〉	통과 (3.08ms, 10.9MB)
테스트 11 〉	통과 (10.32ms, 11MB)
테스트 12 〉	통과 (7.98ms, 10.9MB)
테스트 13 〉	통과 (2.68ms, 11MB)
테스트 14 〉	통과 (12.36ms, 11.1MB)
효율성  테스트
테스트 1 〉	통과 (900.16ms, 71.9MB)
테스트 2 〉	통과 (1239.22ms, 141MB)
테스트 3 〉	통과 (886.71ms, 88.5MB)
테스트 4 〉	통과 (917.70ms, 82.7MB)
테스트 5 〉	통과 (1616.35ms, 188MB)
테스트 6 〉	통과 (1265.78ms, 122MB)