효율적인 화폐구성(p.226) - 다이나믹 프로그래밍(이코테)

---

해설 부분은 책의 내용을 포함하고, 더 추가하여 최대한 자세하게 설명하려고 노력했습니다.

---

 

문제 설명

 

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

 

입력 조건 

 

• 첫째 줄에 N, M이 주어진다.(1<= N <= 100, 1 <= M <= 10,000) 
• 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다. 

 

출력 조건

 

• 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다. 
• 불가능할 때는 -1을 출력한다. 

 

입력 예시 1

 

2 15
2
3

 

출력 예시 1

 

5

 

입력 예시 2

 

3 4
3
5
7

 

출력 예시 2

 

-1

 

 

 

---

 

문제 해설 

 

실전 문제의 마지막 다이나믹 프로그래밍 문제다. 이 또한 앞 문제들과 마찬가지로 횟수를 저장할 dp 테이블을 초기화 해서 밑에서 부터 올라가는 바텀업 방식으로 문제를 해결하면 된다. 저자는 앞서 나온 거스름돈 문제와 비슷하지만 큰 단위의 화폐가 작은 단위 화폐의 배수가 아니라는 점에서 그리디문제가 아니라고 했다. 큰 화폐부터 채우는 방식으로는 최소의 결과값을 출력할 수 없기 때문에 그렇다. 

 

책에서 제시한 점화식은 다음과 같다.

 

a_i = min(a_i, a_i-k + 1) 

 

i는 현재의 인덱스이고 k는 현재세고 있는 기준 화폐이다. 

 

앞 문제와의 차이점이 있다면 인덱스를 돌리는 반복문 하나, 기준 화폐를 돌리는 반복문 하나 총 2개가 필요하다는 것이다

 

책에서 제시한 해설 코드는 다음과 같다. 

 

n, m = map(int, input().split()) 
# N개의 화페 단위 입력받기 
array = [] 
for i in range(n):
  array.append(int(input())) 

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

# 다이나믹 프로그래밍 진행(보텀업) 
d[0] = 0
for i in range(n): # 작은 화페부터 하나씩 진행 ( 순서대로 입력될 것이라고 생각 ) 
  for j in range(array[i], m + 1): 
    if d[j - array[i]] != 10001: # a(i-k) 값이 이전에 한번이라도 조정이 되었다면(초기값이 아니라면) 
      # min함수안에 d[j]를 넣는 이유 : 이전에 반복문을 돌린 금액(array[i])의 조합이 더 작은 수 일수 있어서
      d[j] = min(d[j], d[j - array[i]] + 1) 

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

# a(i-k)인 이유 : k는 지금 세고 있는 화페의 단위 
# a(7- 5) = a(2)가 존재하면(10001이 아니면) a(2)에 k(지금은 5)를 추가해서 2 + 5가 되기 때문에
# 그래서 a(2)인 a(i-k)에 +1을 해주면서 최소의 횟수를 추가해준다.

 

효율적인 화폐 구성이라는 제목에 알맞은 효율적이고 간결한 코드다.

 

d = [10001] * (m + 1) 에서 10001인 이유는 최솟값을 구하는 것이 점화식이기 때문에 가장 큰 값으로 초기화를 해주는 것이고, (m + 1)인 이유는 마지막에 d[m]을 출력하고 인덱스 1부터 시작할 것이기 때문이다. 

 

d[0] = 0은 화폐단위 0원으로는 아무것도 만들 수 없기 때문에 개수가 0이 된다. 

 

반복문 코드를 한줄 한 줄 따라가 보자. 

 

for i in range(n):

# 후에 array[i] 나옴

 

첫 반복문이 0에서 n까지 반복인 이유는 array리스트 안에 저장된 기준 화폐 수만큼 반복하기 위함이다. 

 

for j in range(array[i], m + 1):

 

array[i]는 입력된 기준 화폐를 의미하는데 array[i]부터 시작하는 이유는 점화식이 ai = min(ai, ai-k + 1) 인데 현재 기준 화폐의 크기(array[i])보다 작은 수부터는 시작할 수 없기 때문이다. 따라서 2번째 줄은 array[i]부터 시작하고 마지막까지 가는 바텀업 방식이므로 m까지 반복한다. 

 

if d[j - array[i]] != 10001:

 

i - k 원을 만들 수 있는 경우에만 최솟값 갱신을 해주기 위해 if문으로 조건을 걸었다. 

 

d[j] = min(d[j], d[j - array[i]] + 1)

 

d[i]가 아닌 d[j]로 설정해야지 기준 화폐를 인덱스로 하는 값부터 시작이 가능하다. 또 d[j - array[i]] + 1은 기준 화폐만큼의 인덱스를 빼주고 그 값에 +1을 하면 동전 횟수 하나를 추가하는 식이 되기에 그렇다.

 

쉽게 말해 7원을 만들고 기준화폐가 5원이라면 7-5 = 2, d[2] 의 값이 1이면 d[2] + 1 해서 동전 '2'개로 7원을 만들 수 있다는 뜻이다.