문제
화폐의 단위가 배열 $a$로 주어지고 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 $m$원이 되도록 하려고 합니다. 각 화폐를 중복해서 사용할 수 있습니다. $m$원을 만들기 위한 최소한의 화폐개수를 구하는 문제입니다. $m$원을 만들 수 없을 때는 -1을 return합니다.
1. a = [2,3], m = 15
=> 5
2. a = [3], m = 4
=> -1풀이
1번 문제부터 생각해보겠습니다. 15를 만드는 경우의 수는 [2,2,2,3,3,3], [3,3,3,3,3],[2,2,2,2,2,2,3] 의 3가지가 있는데 이중 [3,3,3,3,3]이 개수가 제일 적어 답은 5가 됩니다.
먼저, 화폐단위보다 작은 $m$은 조합을 만들 수 없기 때문에 -1을 return합니다. $m$을 만들기 위한 최소한의 화폐개수는 어떻게 될까요? 1번 문제의 [2,3]이 화폐 단위라면 $m-2$의 최소한의 화폐개수와 $m-3$의 최소한의 화폐개수 중 최소값에서 1을 더하면 됩니다. 따라서, 이 문제는 다이나믹 프로그래밍으로 해결할 수 있습니다. 최적 부분 구조와 중복된 하위문제의 조건을 만족하기 때문이죠.
다이나믹 프로그래밍으로 문제를 해결하기 위해서는 어떠한 방식으로든 각 $m$값에 대한 dp table을 작성해야 합니다. 그렇다면 dp table에 담기는 값은 해당 $m$을 얻기 위한 최소한의 화폐개수가 되겠죠.
화폐개수가 여러 개이므로 각 화폐단위마다 dp table을 완성하는 형태로 진행해 보도록 하겠습니다. 화폐단위를 여러 개 동시에 비교하는 것이 아니므로 예를 들어 '2' 화폐단위에 대해서 dp table을 완성할 때, $m$의 최소한의 화폐개수와 $m-2$의 최소한의 화폐개수 + 1 의 값 중 최소값을 담으면 될 것 같습니다. dp table의 $m-2$ 값에 1을 더하는 이유는 해당 화폐단위가 한 개 추가되어 $m$을 만들기 때문입니다. 그리고 그 다음 화폐단위에 대해서 dp table을 완성시키면 될 것 같습니다.
kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다.
홍머스 정리
- 다이나믹 프로그래밍
- 난이도: 상, 방법론 생각하기가 까다로움
- 온사이트 코딩 인터뷰라면 이 정도까지는....?
참조
'Computer > Coding Test' 카테고리의 다른 글
| 코딩테스트 문제 (11) - 비밀 지도 (0) | 2021.02.24 |
|---|---|
| 코딩테스트 문제 (10) - 배열의 K 번째 큰 요소 (0) | 2021.02.24 |
| 코딩테스트 문제 (8) - 개미 전사 (0) | 2021.02.24 |
| 코딩테스트 문제 (7) - 계단 오르기 (0) | 2021.02.24 |
| 코딩테스트 문제 (6) - 연속적으로 반복되는 최대 문자열 길이 (0) | 2021.02.23 |
