9084. 동전

문제

백준 9084번 동전

---

풀이

dp 기본문제. 피곤해서 머리가 느릿느릿 안돌아간다아ㅏ

리스트 dp를 만들어야하는 금액 m만큼 모두 0으로 초기화해놓는다.
리스트 원소를 i-c(동전의 금액)으로 접근할 것이기 때문에 편의상 dp[0]에 1을 저장한다.

그 다음으로는 각 동전마다 dp의 값들을 갱신해준다.

T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    coin = list(map(int, sys.stdin.readline().split()))
    m = int(sys.stdin.readline())

    dp = [0] * (m+1)
    dp[0] = 1
    for c in coin:
        for i in range(c, m+1):
            dp[i] += dp[i-c]
    print(dp[m])