-
518. Coin Change 2(Python, LeetCode Medium)LeetCode 2022. 9. 4. 22:49
문제 설명
주어진 동전을 이용하여 주어진 금액을 만드는 방법의 수를 반환하세요!
입력
coins: 동전의 종류를 의미하는 1차원 리스트
amount: 구성해야하는 총 금액
풀이
만약, [1, 2]원의 코인으로 3원을 만든다고 할 때,
1원은 0 → 1, 1 → 2, 2 → 3의 경우에 사용할 수 있으며,
2원은 0 → 2, 1 → 3의 경우에 사용할 수 있습니다.
동전을 하나씩 차례로 순회하며, 해당 동전의 크기만큼을 뺀 위치에 있는 숫자를 현재 위치에 더하는 방법으로 접근할 수 있습니다.
코드
더보기from typing import List class Solution: def change(self, amount: int, coins: List[int]) -> int: dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: for i in range(coin, amount + 1): dp[i] += dp[i - coin] return dp[-1] if __name__ == '__main__': solution = Solution() result = solution.change(amount=5, coins=[1, 2, 5]) print(4 == result, result) result = solution.change(amount=3, coins=[2]) print(0 == result, result) result = solution.change(amount=10, coins=[10]) print(1 == result, result)
'LeetCode' 카테고리의 다른 글
(임시) 967. Numbers With Same Consecutive Differences(Python, LeetCode Medium) (0) 2022.09.08 (임시)94. Binary Tree Inorder Traversal(Python, LeetCode Easy) (0) 2022.09.08 606. Construct String from Binary Tree(Python, LeetCode Easy) (0) 2022.09.07 814. Binary Tree Pruning(Python, LeetCode Medium) (0) 2022.09.06 429. N-ary Tree Level Order Traversal(Python, LeetCode Medium) (0) 2022.09.06