엔지니어 게시판
LeetCode 솔루션 분류

# [5/21] 322. Coin Change

• mingki 작성
• 작성일

• 441 조회
• 2 댓글

### 본문

[LeetCode 시즌 3] 2022년 5월 21일 문제입니다.

322. Coin Change
Medium

You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money.

Return 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.

Example 1:

```Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
```

Example 2:

```Input: coins = [2], amount = 3
Output: -1
```

Example 3:

```Input: coins = [1], amount = 0
Output: 0
```

Constraints:

• `1 <= coins.length <= 12`
• `1 <= coins[i] <= 231 - 1`
• `0 <= amount <= 104`

댓글 2

## coderoncruise님의 댓글

• coderoncruise
• 작성일
dynamic programming - bottom up
- compute all minimum counts up to 'amount'
- TC: O(amount * N of coins)
- SC: O(amount) for memoization table

``````class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float("inf")] * (amount + 1)
dp[0] = 0

for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)

return dp[-1] if dp[-1] != float("inf") else -1``````

## mingki님의 댓글

• mingki
• 작성일
C++
Runtime: 143 ms, faster than 39.70% of C++ online submissions for Coin Change.
Memory Usage: 14.3 MB, less than 73.09% of C++ online submissions for Coin Change.
``````class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, 1e9);
int n = coins.size();

dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int j = 0; j < n; ++j) {
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};``````
전체 128 / 1 페이지

### 새댓글

• 등록자 JakeMinSVK 등록일 18:25
• 등록자 JakeMinSVK 등록일 18:24
• 등록자 학부유학생 등록일 06.22
• 등록자 학부유학생 등록일 06.21
• 등록자 Coffee 등록일 06.21
• 등록자 Coffee 등록일 06.21
• 등록자 SVKOREANS 등록일 06.20
• 등록자 학부유학생 등록일 06.20
• 등록자 Coffee 등록일 06.20
• 등록자 키위 등록일 06.20