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

• N가지 종류의 화폐가 있습니다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 합니다. 이때 각 화폐는 몇 개라도 사용할 수 있습니다.
• 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분합니다.
• 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수입니다.
• M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하세요.

<문제> 효율적인 화폐 구성: 문제조건

<문제> 효율적인 화폐 구성: 문제 해결 아이디어

• ai = 금액 i를 만들 수 있는 최소한의 화폐 개수
• k = 각 화폐의 단위
• 점화식: 각 화폐 단위인 k를 하나씩 확인하며
  • a_i-k를 만드는 방법이 존재하는 경우, a_i=min(a_i,a_i-k+1)
  • a_i-k를 만드는 방법이 존재하지 않는 경우, a_i=INF

• 𝑁 = 3, 𝑀 = 7이고, 각 화폐의 단위가 2, 3, 5인 경우 확인해 봅시다.
• Step 0 (초기화)
  • 먼저 각 인덱스에 해당하는 값을 INF(무한)의 값을 설정합니다.
  • INF은 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미를 가집니다.
  • 본 문제에서는 10,001을 사용할 수 있습니다.

• Step 1
  • 첫 번째 화폐 단위인 2를 확인합니다.
  • 점화식에 따라서 다음과 같이 리스트가 갱신됩니다.

• Step 2
  • 두 번째 화폐 단위인 3을 확인합니다.
  • 점화식에 따라서 다음과 같이 리스트가 갱신됩니다.

• Step 3
  • 세 번째 화폐 단위인 5를 확인합니다.
  • 점화식에 따라서 다음과 같이 최종적으로 리스트가 갱신됩니다.

<문제> 효율적인 화폐 구성: 답안 예시 (Python)

# 정수 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])