[Algorithm] 이것이 코딩 테스트다 - 효율적인 화폐 구성

교재 : 이것이 코딩 테스트다 with 파이썬
chapter 8 다이나믹 프로그래밍
실전문제 8-5 효율적인 화폐 구성 p.226
그리디 동전문제만 풀고 싶어

 

효율적인 화폐 구성

문제

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

입력 조건

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

출력 조건

• 첫째 줄에 경우의 수 X를 출력한다.
• 불가능할 때는 -1을 출력한다.

입력 예시

2 15
2
3

출력 예시

5

 

문제 해설

주어진 N가지 종류의 화폐를 최소 개수로 이용하여 그 값의 합이 M원이 되도록 하는 경우의 수를 구하는 문제이다. 각 화폐는 무한정으로 사용할 수 있으며, 화폐의 순서만 다른 것은 같은 경우로 간주한다. DP 테이블을 이용하여 각 값에 도달할 수 있는 최소 화폐 개수를 저장하면서 문제를 해결했다. 이전에 풀어봤던 거스름돈 문제와 비슷해 보이지만 화폐 단위가 큰 단위가 아니라 작은 단위의 배수라는 것이 다르다.  가장 큰 화폐부터 처리하는 방법으로는 처리할 수 없기에 다이나믹 프로그래밍을 이용해야 한다.

 

책에 있는 점화식은 위와 같다. i 는 현재 인덱스, k는 현재 세고 있는 화폐이다.

그리디 알고리즘으로 푼 동전과 다른 점은 인덱스를 돌리는 반복문 하나, 기준이 되는 화폐를 돌리는 반복문 하나 총 두 개의 반복문이 필요하다.  이 점화식을 모든 화폐 단위에 대하여 적용하면 된다. 

 

n, m = map(int, input().split())
array = []
for i in range(n):
    array.append(int(input()))​

n은 동전 종류의 개수, m은 거슬러 줘야 할 금액이다. for 문으로 array 리스트에 각 동전의 가치를 입력받는다. 

 

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

인덱스	0	1	2	3	4	5	6	7
값	0	100,001	100,001	100,001	100,001	100,001	100,001	100,001

문제에서 입력 M의 입력 조건이 최대 10,000 이므로 불가능한 수로 10,001을 설정한다.

아무것도 사용하지 않아도 0원은 0이라 가정해서 값을 대입해줘야 한다.

 

for i in range(n):

 첫 반복문은 array 리스트 안에 저장된 기준 화폐 수만큼 반복하기 위해 n까지 반복해 준다.

i : 화폐 단위 j : 금액

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

현재 기준 화폐의 크기보다 작은 수부터 시작할 수 없기에 array [i]부터 시작한다.  따라서 array [i]는 입력된 기준 화폐이다.

 

 if d[j - array[i]] != 10001: # (i-k)원을 만드는 방법이 존재하는 경우
 	d[j] = min(d[j], d[j - array[i]] + 1)

(i-k) 원을 만들 수 있는 경우에만 최솟값을 갱신하기 위해 조건문을 걸어준다. j원을 만들 수 있는지 검사하며, j-arrray[i] 원을 만들 수 있다면 이를 활용하여 동전의 최소 개수를 갱신한다.

즉 이전에 계산된 값 d[j-array[i]] 에 1을 더한 것이 현재 계산한 d[j] 보다 작을 경우 d[j] 를 해당 값으로 갱신된다. 

예를 들어 N=3, M=7 [2, 3, 5] 인 경우의 테이블은 아래와 같다. 

 

1) 첫 번째 동전인 2를 이용하여 DP 테이블 갱신

인덱스	0	1	2	3	4	5	6	7
값	0	100,001	1	100,001	2	100,001	3	100,001

 

2) 두 번째 동전인 3를 이용하여 DP 테이블 갱신

인덱스	0	1	2	3	4	5	6	7
값	0	100,001	1	1	2	2	2	3

 

3) 세 번째 동전인 5를 이용하여 DP 테이블 갱신

인덱스	0	1	2	3	4	5	6	7
값	0	100,001	1	1	2	1	2	2

이는 2원 1개 5원 1개로 7원을 만들 수 있으므로 더 적은 값으로 7원을 만들 수 있기에 값을 갱신된다.

 

if d[m] == 10001:  # 최종, M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

d [m]에 저장된 값이 10001이라면 거슬러 줄 수 있는 방법이 없는 것이고 그렇지 않으면 최소 동전 개수를 출력하게 된다.

 

최종 코드

n, m = map(int, input().split()) 
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: # (i-k)원을 만드는 방법이 존재하는 경우
      d[j] = min(d[j], d[j - array[i]] + 1) 

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