[BOJ]コイン1

使用するアルゴリズム/データ構造

これはコインの組み合わせ数を求める問題です.
硬貨の使用範囲が広がるにつれて、それぞれの金額を創出できれば、dpを積算して使用します.
外環のコインはコインごとに循環します.
最初のコイン->1,2コイン->1,2,3コインのみ使用...
上記の手順で使用するコインの種類を徐々に増やしていきます.
内輪の価格は総金額をコイン元からk元に巡回する.
前のコインで求めた数字を用いて、新しいコインをdp[price]に追加するために必要な数字を求める.

コード#コード#

from sys import stdin
input = stdin.readline

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
dp = [0 for _ in range(k+1)]
dp[0] = 1

for coin in coins:
    for price in range(coin, k+1):
        dp[price] += dp[price-coin]
print(dp[k])