[Python] BOJ 9084 : 동전

https://www.acmicpc.net/problem/9084 < - click

요구사항

1. 시간 제한 1초 
   1. 코인의 종류와 주어진 금액을 만드는 모든 방법, N과 M 따라서 O(N*M) 이 되겠다. 20 * 10000 이니 2만정도.. O(NlogN)정도
2. 메모리 제한 128MB
   1. 메모리 제한은 128MB로 터지진 않을 거 같다. 이유는 리스트의 크기가 해봐야 dp 테이블 M+1 개, 이니깐.
3. 동전의 종류가 주어질 때, 주어진 금액을 만드는 모든 방법을 세는 프로그램

설계

1. 처음엔, 2차원 DP 테이블을 만들어서 하려고 하니 너무 복잡해서 다른 관점에서 보려고 노력했다. 
2. 따라서 동전의 종류가 주어질 때, 주어진 금액을 만드는 모든 방법을 세는 함수의 로직은
3. 1차원 DP 테이블을 초기화 한다.  dp = [0] * (주어진 금액 + 1)
4. dp[0] 은 1이다. 그 이유는 모든 동전으로 0원을 만들 수 있기 때문이다. (그렇게 가정해야됨)
5. for coin in coin_type: 여기서 coin_type 은 동전의 종류이다. 
6. for amount in  range(coin, money+1) 여기서 coin  부터 시작하는 이유는 동전의 종류 이전은 못 만들기 때문이다.
   1. ex) 동전의 종류 2원, 만들어야할 금액 4원 이면 2원으로 1원을 못 만드니 의미가 없다는 말.
7. dp[amount] += dp[amount - coin], 만들어야 할 금액을 몇 번 만들 수 있는 지 count 하기 때문에 이와 같은 로직으로 처리해준다. 
   1. 만들어야할 금액 8원, 동전의 종류 2원 4원 이라고 했을 때.
   2. dp[0] = 1, dp = [1, 0, 0, 0, 0, 0, 0, 0 ,0]  초기값
   3. for coin in coin_type: coin = 2
   4. for amount in range(coin, money+1): amount = 2
   5. dp[2] = dp[2] + dp[2-2] -> dp[2] = dp[0] -> dp[2] = 1이 된다.
   6. dp[1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
   7. coin = 2, amount = 3 일 때
   8. dp[3] = d[3] + d[3-1] 따라서 dp[3] = 0이 된다. 
   9. coint =2, amoint = 4 를 (2, 4) 라고 쓰겠다. 
   10. dp[4] = dp[4] + dp[4-2] = 1
   11. (2, 5) dp[5] = dp[5] + dp[5-2] = 0
   12. 위 과정을 반복하면 coin = 2일 때, dp = [1, 0, 1, 0, 1, 0, 1, 0, 1] 이 된다.
   13. (4, 4) 일 때 dp[4] = dp[4] + dp[0] = 1 + 1 = dp[4] = 2
   14.  위 과정을 반복한다. 그러면 마지막으로 만들어야 할 금액 즉 money를 출력.    

구현

import sys
input = lambda: sys.stdin.readline().rstrip()

def coin_count(coin_type, money):
    dp = [0] * (money + 1)
    dp[0] = 1

    for coin in coin_type:
        for amount in range(coin, money + 1):
            dp[amount] += dp[amount - coin]
    return dp[money]

test_case = int(input())

for _ in range(test_case):
    N = int(input())
    coin_type = map(int, input().split())
    money = int(input())

    print(coin_count(coin_type, money))