[다이나믹 프로그래밍] 효율적인 화폐 구성 - 파이썬(python)

효율적인 화폐 구성

난이도 : 中 풀이 시간 : 30분

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

해답

 

n, m = map(int, input().split())

array = []
for i in range(n):
    array.append(int(input()))

d = [99999] * (m+1)
d[0] = 0

for i in range(n):
    for j in range(array[i], m+1):
        d[j] = min(d[j], d[j-array[i]] + 1)

if d[m] == 99999:
    print(-1)
else:
    print(d[m])

---

예시

 

# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

---

해설

 

적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾아야 합니다.
금액 i를 만들 수 있는 최소한의 화폐 개수를 a[i], 화폐의 단위를 k라고 할 때 점화식을 만들 수 있습니다.
a[i] = min(a[i], a[i-k]+1) 이므로 이 점화식을 모든 화폐 단위에 대하여 적용하면 됩니다.