[DP] 다이나믹 프로그래밍 (5) 실전 문제 - 효율적인 화폐 구성 ⭐

이코테 p.226 실전 문제 - 효율적인 화폐 구성

입력 예시

3 7 2 3 5

출력 예시

2

내 소스코드

• 점화식 a(i) = min(a(i - money[0]), a(i - money[1]), a(i - money[2]), ...)  + 1
• 최솟값을 구하기 위해 DP 리스트를 INF로 초기화

# 입력 받기
n, m = map(int, input().split())
money_list = list(map(int, input().split()))

INF = 10001
dp = [INF] * (m + 1)
# 자기 자신에 대해서는 최소 화폐 개수 1개
for money in money_list:
  dp[money] = 1

for i in range(min(money_list), m + 1):
  min_money = INF
  for money in money_list:
    if (i - money) >= 0 and min_money > dp[i - money]:
      min_money = dp[i - money]
  min_money += 1
  if dp[i] > min_money:
    dp[i] = min_money

if dp[m] == INF:
  print(-1)
else:
  print(dp[m])

교재 소스코드

• 그리디의 거스름돈 문제와 거의 동일하지만, 큰 화폐 단위가 작은 화폐 단위의 배수가 아님
  • 그렇기 때문에 그리디처럼 가장 큰 화폐 단위부터 처리하는 방법은 적용이 불가하며, 다이나믹 프로그래밍을 이용해야 함
• 적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 됨
  • 금액 i를 만들 수 있는 최소한의 화폐 개수를 a(i), 화폐 단위를 k라고 할 때, 점화식은 다음과 같음
    • a(i - k)를 만드는 방법이 존재하는 경우, a(i) = min(a(i), a(i - k) + 1)
    • a(i - k)를 만드는 방법이 존재하지 않는 경우, a(i) = 10,001
    • 이때, a(i - k)는 금액 (i - k)를 만들 수 있는 최소한의 화폐 개수를 의미함
• 문제를 풀기 위해서는 가장 먼저 K의 크기만큼 리스트를 할당하고, 각 인덱스를 '금액'으로 고려하여 메모이제이션 진행
• 구체적인 동작 예시: N = 3, M = 7, 각 화폐 단위가 [2, 3, 5]인 경우
  1. 초기화 수행
     1. DP 리스트를 만든 후, 각 인덱스에 해당하는 값으로 10,001을 설정
     2. 10,001은 특정 금액을 만들 수 있는 화폐 구성이 없다는 뜻
     3. 0원의 경우, 화폐를 하나도 사용하지 않았을 때 만들 수 있으므로 dp[0] = 0
  2. 화폐 단위 [2, 3, 5] 중 2부터 확인
     1. 점화식 적용
     2. ex) 2원은 2원짜리 하나를 이용하여 만들 수 있으므로 a(2) = a(0) + 1 = 1
     3. ex) 4원은 2원짜리 두개를 이용하여 만들 수 있으므로 a(4) = a(2) + 1 = 2
  3. 화폐 단위 3 확인
     1. 점화식 적용
     2. ex) 3원은 3원짜리 하나를 이용하여 만들 수 있으므로 a(3) = a(0) + 1 = 1
     3. ex) 5원은 2원짜리 하나, 3원짜리 하나를 이용하여 만들 수 있으므로 a(5) = a(2) + 1 = 2
     4. ex) 6원은 3원짜리 두개를 이용하여 만들 수 있으므로 a(6) = a(3) + 1 = 2
     5. ex) 7원은 2원짜리 두개, 3원짜리 한개를 이용하여 만들 수 있으므로 a(7) = a(4) + 1 = 3
  4. 화폐 단위 5 확인
     1. 점화식 적용
     2. ex) 7원은 5원짜리 하나, 2원짜리 하나를 이용하여 만들 수 있으므로 a(7) = min(a(7), a(2) + 1) = 2 ⬅️ 기존의 3에서 2로 갱신됨
  5. 최종적으로 a(7) = 2이므로 최소한의 화폐 개수는 2
• 소스코드

# 입력 받기
n, m = map(int, input().split())
money_list = list(map(int, input().split()))

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

# 다이나믹 프로그래밍 진행 (바텀업 방식)
dp[0] = 0
for i in range(n):
  for j in range(money_list[i], m + 1):
    dp[j] = min(dp[j], dp[j - money_list[i]] + 1)

if dp[m] == INF: # 최종적으로 m원을 만드는 방법이 없는 경우
  print(-1)
else:
  print(dp[m])