競プロ初中級者100問

DPL1A コイン問題

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A&lang=ja

この問題は動的計画法を用いて解くことができます。

方針

dp[m][n]を考えます。このリストは総額がnとなるようにm番目までのコインを選んだ時の枚数の最小値を表します。

コード

DPL1C ナップザック問題とほとんど同じコードになります。
最大値ではなく最小値を更新していく点に注意してください。

貰うDP

1
2
3
4
5
　                 dp[m+1][n-C[m]]
                       |
                       |
                       ↓
dp[m][n] --------> dp[m+1][n]

dp[m+1][n-C[m]]が配列外参照になるかの判定が必要です。

1
2
3
4
5
6
7
8
9
10
11
12
N, M = map(int, input().split())
C = list(map(int,input().split()))
INF = 10**10
dp = [[INF]*(N+1) for _ in range(M+1)]
dp[0][0] = 0
for m in range(M):
    for n in range(N+1):
        if n-C[m]>=0:
            dp[m+1][n] = min(dp[m+1][n-C[m]]+1, dp[m][n])
        else:
            dp[m+1][n] = dp[m][n]
print (dp[M][N])

記事情報

  • 投稿日：2020年5月14日
  • 最終更新日：2020年5月14日