[Leetcode] Coin Change (DP) - java

Coin Change - LeetCode

문제 파악

coins에는 현재 가지고 있는 동전이 들어있다. amount는 만들어야 하는 금액인데, 주어진 동전들로 이 금액을 만드는 문제

 

amount가 0이면 0, 주어진 동전들로 만들 수 있는 금액이 아니라면 -1을 반환한다. (coin이 0인 경우는 없다.)

---

접근 방법

0원부터 11원까지 만들 수 있는 동전의 최소 필요 수를 dp에 저장한다.

11원을 만들려면? 3가지 선택지가 있음. 10원 + 1원, 6원 + 5원, 9원 + 2원이 된다.

이 중에서 동전이 최소로 드는 경우를 찾는다.

dp에는 필요한 최소 동전 수가 저장되어있다.

점화식으로 나타내면 $dp(i) = min(dp(i-coin) + 1)$ 이 된다.

 

내가 처음에 실수한 포인트는 쪼개면서 amount에서 바로 coin을 뺀 점이다.

배열에 저장하지 않고 빼다 보니까 amount가 덮어씌워져서 오류가 생김;;;

 

배열에 amount+1로 채우는 이유는 만들 수 없는 값으로 넣어서 불가능을 표시하기 위함이다.

---

코드 구현

class Solution {
    public int coinChange(int[] coins, int amount) {

        // 1. 초기화
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount+1);
        dp[0] = 0; // base 조건

        // 2. 점화식 
        for(int i =1; i <= amount; i++){
            for(int coin : coins){
                if(coin <= i){
                    dp[i] = Math.min(dp[i], dp[i-coin]+1);
                }
            }
        }

        // 3. 결과 반환
        return dp[amount] < amount+1 ? dp[amount] : -1;
    }
}

---

배우게 된 점

점화식 세우는 게 중요하다는 점, DP 배열을 잘 짜는게 중요하는 점을 배울 수 있었다.