10. 동전 교환 (냅색 알고리즘)
생성일: 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])
Author And Source
이 문제에 관하여(10. 동전 교환 (냅색 알고리즘)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lsj8706/10.-동전-교환-냅색-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)