[Python] 백준 2624번: 동전 바꿔주기

https://www.acmicpc.net/problem/2624

2624번: 동전 바꿔주기

동전의 갯수가 정해져있기 때문에 이전행에 동전의 갯수(cnt) * 금액(val) 만큼 dp를 더해주면된다

점화식은 dp[i][j] = dp[i][j] + dp[i-1][j-v*val] ( 1 <= v <= cnt)

T = int(input())
k = int(input())
coin = [[0, 0]]
dp = [[0 for _ in range(T+1)] for _ in range(k+1)]
for _ in range(k):
    x, y = map(int, input().split())
    coin.append([x, y])

dp[0][0] = 1
for i in range(1, k+1):
    val, cnt = coin[i]
    for j in range(T+1):
        dp[i][j] = dp[i-1][j]
        for v in range(1, cnt+1):
            if j-v*val >= 0:
                dp[i][j] += dp[i-1][j-v*val]
            else:
                break

print(dp[k][T])