[백준] 9048번 동전(python)

문제)

 

알고리즘)

DP

- 기준 값은 목표 금액(d), 계산 순서는 오름차순 동전 값(coins)

 

ex)

   c = 3 (현재 동전)

   d[5] += d[5-3] 

   목표 금액 5 += 3원을 사용하기 전의 d[2]의 값 

 

모든 계산을 마치고 목표금액의 마지막 값을 출력 

코드)

#동전
import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n = int(input())
    coins = list(map(int, input().split()))
    goal = int(input())

    d = [0]*(goal+1) #goal(목표 금액)까지 DP 
    d[0] = 1

    for c in coins: #오름차순 코인
        for i in range(c, goal+1): 
            d[i] += d[i-c]  # 현재 i 는 (i- 현재 동전금액) => 이전 목표금액 달성 방법 수

    print(d[goal]) #목표 금액 달성방법