[Dynamic Programming] 동전바꾸기 - 초급

유튭 링ㅋ

 

 

📋 LeetCode 322번

Coin Change - LeetCode

 

F(n)이 합해서 n이 되는 coins의 합이라고 정해준다.

 

F(11)이 되는 경우의 수는 ( F(11-1) or F(11-2) or F(11-5) ) 그리고 저 경우의 수에서 동전 하나를 더한 값이기 때문에 + 1도 해준다.

 

$$ F(n) = min( F(n-1), F(n-2), F(n-5) ) + 1 $$ 

만약 F(1)과 같이 주어진 coin들로 구성할 수 없는 수가 나오면 F의 값을 저장해는 array에 -1 을 넣어준다.

min의 값을 비교할 때, 해당 값이 -1인지 확인해준다.

 

 

👩🏻‍💻 내 풀이

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        arr = [0]
        
	# amount가 0이라면 계산할 필요 없으니까 바로 return
        if amount == 0:
            return 0
    	
        for i in range(1,amount+1):
            min_i = []
            
	# 갖고있는 coin 별로 계산해준다..
            for j in range(len(coins)):
                if i-coins[j] < 0: 
			# 구해야하는 수가 coin 값보다 작으면 패스
                    continue
                elif i-coins[j] >= 0: 
			# 코인보다 크다면 arr 검사
                    if arr[i-coins[j]] == -1:
                        continue
                    else:
			# 저장한 arr에 값이 -1이 아니라면 + 1
                        min_i.append(arr[i-coins[j]]+1) 
            
            if len(min_i)<1: 
		# 저장할게 없다면 -1
                arr.append(-1)
            else:
		# if는 코드 수정하다가 못지운 부분인데 필요 없을듯?
                if min(min_i) == -1: 
                    arr.append(-1)
                else:
		# 저장한 값들 중 최솟값
                    arr.append(min(min_i)) 
        return arr[-1]

 

다른 사람의 풀이