https://leetcode.com/problems/coin-change/description/?envType=study-plan-v2&envId=top-interview-150
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
BFS 풀이
from collections import deque
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
coins.sort(reverse=True)
if amount % coins[0] == 0:
return amount // coins[0]
queue = deque()
queue.append((0, 0)) #현재까지의 값, 갯수
visited = set()
while queue:
now_amount, cnt = queue.popleft()
if now_amount == amount:
return cnt
if now_amount in visited:
continue
visited.add(now_amount)
for c in coins:
if now_amount + c <= amount:
queue.append((now_amount + c, cnt + 1))
return -1
visited로 큰 수로 이미 만든 수 인 경우 탐색을 멈추게하였다.
DP 풀이
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [0] + [amount + 1] * amount
for coin in coins:
for i in range(coin, amount+1):
dp[i] = min(dp[i], dp[i-coin] + 1)
return dp[amount] if dp[amount] < amount +1 else -1
둘 다 시간복잡도는 O(coins*amount) 이다.
visited로 반복연산 제거 안해주면 O(coins^amount)
'Coding Test > Python' 카테고리의 다른 글
[프로그래머스] 큰 수 만들기 (level2, python) (0) | 2024.01.23 |
---|---|
[프로그래머스] 체육복(level1, python) (0) | 2024.01.23 |
[프로그래머스] 카펫 (level2, python) (1) | 2024.01.23 |
[프로그래머스] 소수 찾기 (level 2, Python) (1) | 2024.01.22 |
[프로그래머스] 여행경로 (level3, python) (0) | 2024.01.22 |