AOJ DPL_1_A Coin Changing Problem

備忘録

問題

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

回答

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    coin = il()
    dp = [INF] * (N + 1)

    dp[0] = 0
    for i in range(M):
        for j in range(1, N + 1):
            if 0 <= j - coin[i]:
                dp[j] = min(dp[j], dp[j - coin[i]] + 1)
    print(dp[-1])


if __name__ == '__main__':
    main()

考え方

螺旋本より、動的計画法の問題。
N円の支払いを行うときに必要なコインの最小枚数を求める。

---

要素をN+1個持った配列をINFで初期化し、動的計画法を行う。
コインをi(0 <= i < M)枚使用したとき、j(0 <= j <= N+1)円支払うために必要なコインの枚数を求める。
jが0の時は、支払う必要がないため、0で初期化を行う。
以降は、ゼロから順に、1円支払うために、1枚目のコインの必要な枚数、2円支払うために、1枚目のコインの必要な枚数、 .... 、N+1円支払うために1枚目のコインの必要な枚数を求める。
後は1円支払うために、1枚目のコインと2枚目のコインの必要な枚数、 ... 、N+1枚目のコインと2枚目のコインの必要な枚数
1円支払うために、1枚目のコインと2枚目のコインと3枚目のコインの必要な枚数、 ... 、N+1枚目のコインと2枚目のコインと3枚目のコインの必要な枚数...
と順に求め、i(0 <= i < M)目までのコインを使用したとき、j(0 <= j <= N+1)円支払うための必要なコインの最小枚数を求める。