[leetcode] Coin Change

Coin Change

생각한 방식

• 1부터 amount까지 DP에 값 저장
  ⇢ coins에 있는 값과 관계 없이 돌아서 O(N2)

풀잇법

DP에는 최소로 필요한 동전의 개수를 저장할 것이다.

coins에 있는 종류만 쓸 수 있기 때문에 amount를 채우려면 하나는 무조건 써야 한다. coins에 있는 coin 하나를 선택해서 사용할 때, 나머지 금액을 채우기 위해 필요한 동전의 개수를 최소화하면 된다.

• 금액에 딱 맞는 동전이 있을 때는 하나만 있으면 있으면 된다.
  • 아래의 코드에서 DP[a] = 1
• 아니라면, 나머지 금액에서 사용되는 코인의 개수에 선택했던 코인 1개를 더한다.
  • 아래의 코드에서 DP[a] = min(DP[a], DP[a-c] + 1)

코드

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0: return 0
        
        DP = [2**31 - 1] * (amount + 1)
        
        for a in range(1, amount+1):
            for c in coins:
                if a-c == 0:
                    DP[a] = 1
                elif a-c > 0:
                    DP[a] = min(DP[a], DP[a-c] + 1)
                
        return DP[-1] if DP[-1] != (2**31 -1) else -1

if문으로 따로 안 나눠줘도 된다. a-c == 0일 때 min값은 1이 될 것이기 때문이다.

참고 자료

NeetCode's Youtube