다이나믹 프로그래밍 (Dynamic Programming) (5) - 실전문제 8.5) 효율적인 화폐 구성

문제)

N가지 화폐 종류가 주어진다. 이 화폐들을 사용해서 M원을 만들어야 한다. 이 때 최소한의 화폐 개수를 사용해서 M원을 만들어야 하며 화폐 구성은 같지만 순서가 다른 경우에는 같은 경우로 구분한다.

입력조건)

• 첫째 줄에 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

---

풀이)

이 문제는 바텀업 방식을 통해서 반복문을 M 까지 돌면서 결과 리스트에 화폐 개수를 저장하는 방식으로 해결할 수 있다. 먼저 결과 리스트를 생성하고 무한대로 초기화 한다. 그리고 반복문을 1부터 M까지 돌면서 입력받은 화폐 종류에 대해서도 다시 반복문을 돌린다. 바깥쪽 반복문에 해당하는 인덱스를 i라고 하면 i원을 만들기 위해 결과 리스트의 [i - 화폐 종류]를 비교하여 최솟값을 산출하고 최솟값 + 1 을 인덱스 i에 저장하면 된다. 이 때 1을 더하는 이유는 해당 화폐 1개만 추가하면 i원을 만들 수 있기 때문이다.

i에서 입력 받은 화폐 종류를 뺄 때 0이 되는 경우에는 해당 화폐 1개만 사용하면 i원을 만들 수 있기 때문에 1이 저장되어야 한다. 따라서 결과 리스트의 0번째 인덱스에는 0을 저장하는 방식으로 조건문 없이 위의 최솟값 산출 과정에서 모두 해결 가능하다.