문제

• int 리스트 coins -> 동전 종류
• amount -> total 금액
• 최소한의 동전으로 최종 금액을 만드는 방법
• 동전 수 return
• 만들 수 없다면 -1 return
• 동전의 갯수는 무한하다고 가정

풀이

• 전에 백준에서 dp로 이런 문제 몇 번 풀어봤다

1. amount+1 길이의 리스트를 (최댓값+1)로 초기화
2. 동전으로 만들 수 있는 가장 작은 금액 ~ amount 를 순회한다
3. 순회하면서, 가지고 있는 동전으로 현재 금액을 만들 수 있는 지 확인
4. 가능한 금액 = 이미 가능한 금액 + 동전하나 사용 이라는 점을 명심

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount > 0:
            maxi = 10**4+1
            dp = [maxi for _ in range(amount+1)]
            dp[0] = 0
            new_coin = []
            for coin in coins:
                if coin <= amount:
                    new_coin.append(coin) # amount 보다 큰 동전으로는 불가능 -> 거르기
            if new_coin:
                for target in range(min(new_coin), amount+1):
                    for coin in new_coin:
                    	# 갖고 있는 동전 하나
                        if dp[target-coin] < maxi:
                        	# (현재 금액 - 동전 하나)가 이미 가능한 금액이면
                            dp[target] = min(dp[target], dp[target-coin]+1) # 최솟값일 시 갱신
            if dp[amount] == maxi:
                return -1
            else:
                return dp[amount]
        else:
            return 0

예외

1. 동전이 amount 보다 큰 경우
2. amount 가 0인 경우

결과

시간제한 때문에 고생 좀 했다.
dp 라면 이렇게 전에 만든 금액 + 현재 동전으로 접근하는게 맞는 것 같은데
처음에는 브루트포스 마냥 이전에 만든 모든 금액을 이용해보려 해서 시간이 오래걸렸던 것 같다.
다까먹엇네,,^^,,,,