효율적인 화폐 구성

1. 문제 설명

N 종류의 화폐가 있다. 이 화폐의 개수를 최소한으로 이용하여 가치의 합이 M원이 되도록 한다. 각 화폐는 몇 개라도 사용이 가능하고, 사용한 화폐의 구성은 같지만 순서만 다른 건 같은 경우로 판별한다.

 

예를 들면, 2원과 3원으로 구성된 경우, 15원을 만들기 위한 최소한의 화폐 개수는 3원 5개이다.

 

입력 조건

 

- 화폐의 종류 N, 주어진 M 원 ( 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000 )

- N번 만큼 화폐의 단위를 각각 입력한다. 

2. 문제 풀이

화폐의 단위가 큰 단위가 작은 단위의 배수가 아니라면, 그리디 문제로 해결할 수 없다. 이 경우 DP 문제로 풀 수 있다. ( 대표적인 유형 )

 

이번엔 화폐의 단위를 작은 단위 -> 큰 단위 순으로 확인하면서 만들수 있는 최소 화폐 개수를 판별한다. 

DP를 해결하기 위해, bottom - up 으로 해결하고, 결과 리스트를 선언한다. 이때 인덱스는 금액을 의미하게 된다.

이는 0 ~ M 인덱스 까지 판별을 하면 된다는 의미이다.

 

점화식을 세우면 다음과 같다.

 

a[i] = 금액 i를 만들 수 있는 최소한의 화폐 개수, 화폐의 단위를 k라고 했을 때

a[i - k] = i-k를 만들 수 있는 최소한의 화폐 개수, 금액 (i - k) 를 만들 수 있는 최소한의 화폐 개수

 

( a[i-k] != 10001, 즉 i를 만들 수 있는 화폐 개수가 있을 때 ) a[i] = min(a[i], a[i-k] + 1)

( a[i-k]를 만드는 방법이 없을 경우 ) a[i] = 10001

 

즉 현재 위치한 금액( i )에서 현재 화폐 단위를 뺀 금액( i-k )은 이전의 화폐 단위로 구성된 금액이거나, 현재 화폐 단위의 배수라고 생각 할 수 있다.

 

과정을 생각해보면 다음과 같다.

 

1) 초기화

인덱스(금액)	0	1	2	3	4	5
값	0	10001	10001	10001	10001	10001

2) 화폐 단위 2

인덱스	0	1	2	3	4	5
값	0	10001	1	10001	2	10001

3) 화폐 단위 3

인덱스	0	1	2	3	4	5
값	0	10001	1	1	2	2

 

4) 화폐 단위 5

인덱스	0	1	2	3	4	5
값	0	10001	1	1	2	1

 

인덱스 5를 보면, 화폐 단위 3에서의 경우를 생각해보자.

5 - 3 = 2, a[2] = 1이고, 계산하면 a[5] = 2가 나온다. 현재 a[5] = 10001 이므로 2로 갱신하게 되는 것이다.

 

이를 코드로 변환하면 다음과 같다.

 

3. 느낀 점

마찬가지로, 표를 그려서 규칙을 찾고 여기서 점화식을 도출하면 문제를 해결 할 수 있다.

 

하지만 규칙은 찾았지만, 이를 점화식으로 바로 바꾸기 쉽지 않다. 때문에 많은 유형을 보고 연습을 하자.