10.コイン交換(発色アルゴリズム)
4093 ワード
作成日:2022年2月25日午後4:38
インプリメンテーションコード
# 동전 교환 (냅색 알고리즘)
import sys
sys.stdin = open("input.txt", "rt")
if __name__ == "__main__":
n = int(input())
coin = list(map(int, input().split()))
money = int(input())
dy = [2147000000]*(money+1) # dy[j]는 j원을 거슬러 주는데 사용된 동전의 최소 개수
dy[0] = 0
for i in range(n):
for j in range(coin[i], money+1):
dy[j] = min(dy[j], dy[j-coin[i]]+1)
print(dy[money])Reference
この問題について(10.コイン交換(発色アルゴリズム)), 我々は、より多くの情報をここで見つけました https://velog.io/@lsj8706/10.-동전-교환-냅색-알고리즘テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol