322. Coin Change - medium
문제
You are given coins of different denominations and a total amount of money amount.
Write a function to compute the fewest number of coins that you need to make up that amount.
If that amount of money cannot be made up by any combination of the coins, return -1.
제한사항
- You may assume that you have an infinite number of each kind of coin.
입출력 예
1
2
3
4
Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
1
2
3
Example 2:
Input: coins = [2], amount = 3
Output: -1
풀이
- DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if(amount < 1)
return 0;
// amount까지의 길이를 가지는 임시 vector 생성
// 비교를 위해 적당히 큰수를 기본으로 가짐
vector<int> item(amount+1, (INT_MAX >> 2));
// coins 벡터에 포함된 coin == amount 일때,
// 최소 coin의 수는 자기 자신인 1임
for(const auto& coin : coins){
if(coin <= amount)
item[coin] = 1;
}
// 값이 1부터 최종 목적인 amount까지 반복
for(auto val = 1 ; val <= amount ; ++val){
// 조합할 각 단위의 coin별로 만들수 있는 최소값을 계산
// coin이 [1,2,5] 일때, val = 10 이라면,
// item[10] = min(item[10], item[10 - 1] + 1)
// item[10] = min(item[10], item[10 - 2] + 1)
// item[10] = min(item[10], item[10 - 5] + 1)
// 즉, 해당 코인으로 만들수 있는 최소값을 각각 계산하여
// 최후의 최소값을 저장
int minVal = INT_MAX;
for(const auto& coin : coins){
if(val - coin >= 0 && item[val - coin] > 0){
item[val] = min(item[val], item[val - coin] + 1);
}
}
}
// 구하고자 하는 amout가 현재 코인으로 만들수 있는 조합이 아니라면,
// 초기에 설정한 적당한 크기의 값이 저장되어 있으므로 이를 -1로 리턴
return item[amount] != (INT_MAX >> 2) ? item[amount] : -1;
}
};