[다이나믹 프로그래밍] ▲ 문제4 - 효율적인 화폐 구성(226p)

[이코테] 문제4 - 효율적인 화폐 구성(226p)

(한줄평) 점화식은 잘 세웠으나 책의 풀이가 더 간결하고 좋았던 문제로 한번쯤 복습이 필요한 문제!

풀이 시간: 40분 이내

---

---

1) 문제 해결 아이디어

이 문제는 그리디 거스름돈 문제와 거의 동일하지만 화폐단위의 큰 단위가 작은 단위의 배수가 아니기 때문에 무조건 큰 단위부터 거슬러주면 안된다!!

금액 1부터 m까지 만들수 있는 최소한의 화폐 개수를 찾아 d에 입력하면 된다.

아래의 점화식을 n개의 화폐 단위에 대하여 차례로 적용하면 된다.

각 금액을 만들 수 있는 최소 화폐 개수를 담는 리스트(d)를 (m + 1)의 크기로 10001로 초기화하여 생성한다.

 

Q. dp테이블을 10001로 초기화하는 이유는?

화폐의 가치는 10,000보다 작은 자연수이고 목표 금액(m)이 1이상 10,000이하이기 때문에 화폐 개수의 최댓값은 10000이다. 그러므로 10001이 아니더라도 10000보다 큰 값으로 먼저 셋팅을 해주면 된다!

처음에는 -1로 셋팅을 해줬는데 그렇게 되면 d[price]가 -1일 경우 min 함수에 의해 -1 값이 채택되는 문제가 발생한다.

 

<점화식>

 

2) 소스코드

n, m = map(int, input().split())  # 화폐 종류, 목표금액
graph = [int(input()) for _ in range(n)]  # n개의 화폐 가치
graph.sort()  # 오름차순 정렬
d = [10001] * (m + 1)  # 최소한의 화폐 개수
d[0] = 0  # 0원을 만들기 위해 필요한 화폐 개수는 0

# n개의 화폐 단위에 대하여
for i in range(n):
  # price를 만들기 위한 최소 화폐 개수 구하기
  for price in range(graph[i], m + 1):
    # (price - 화폐단위)를 만드는 방법이 있으면
    if d[price - graph[i]] != 10001:    
      d[price] = min(d[price], d[price - graph[i]] + 1)

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