[Grind75-LeetCode] Coin Change JAVA

반응형

728x90

[Grind75-LeetCode] Coin Change - Medium

---

접근

• dp

---

풀이

주어진 동전을 가지고 원하는 금액을 만들 수 있는지 만들 수 있다면 최소 몇 개의 동전을 사용해야 하는지 구하는 문제이다. 동전의 개수는 무한대로 주어지고 동전을 100원짜리, 500원짜리처럼 특정 값의 동전이 주어지기 때문에 주어진 값의 동전만 사용해서 만들어야 한다. 원하는 금액을 맞출 수 있으면 만드는데 필요한 최소 동전 개수를 구하고 만들 수 없다면 -1을 반환한다. 문제에 주어지는 내용이 동전일 뿐이지 비슷한 내용의 문제가 매우 많은 전형적인 dp 문제이다. dp 배열을 통해 Bottom-Up 방식으로 값을 채워나가면 해결이 되는 문제이다.

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

순서대로 우선 dp 배열을 만든다. 0번지는 사용을 하지 않고 1번지부터 목푯값까지의 인덱스를 사용한다. 최소 동전 개수를 구하는 게 목표이기 때문에 목푯값 보다 큰 수로 배열을 초기화해 준다.

	for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }

배열을 구성하는 부분이다. 동전의 종류가 정해져 있기 때문에 1번 인덱스부터 순차적으로 배열을 구성하는 것이 아닌 해당 동전마다 만들 수 있는 경우를 체크한다. 예를 들어 동전의 종류가 1, 2, 5 이렇게 3개가 있다면 동전 각각으로 목푯값까지 해당 동전을 사용해 몇 개를 사용해 만들 수 있는지 채워 넣는다. dp [ j - coin ] + 1은 현재 동전을 사용해 인덱스에 해당하는 값을 만들기 위한 최솟값을 나타내는 것으로 현재 j가 8이고 coin이 5라면 3을 만드는 데 필요한 최소 동전 개수에 5라는 동전을 하나 추가하게 되었을 때 8을 만들기 위한 최소 동전 개수가 되므로 dp [3] + 1이 되는 것이다. 만들어진 배열을 통해 목푯값 인덱스에 들어있는 값이 목푯값 보다 클 때 즉 처음 초기화 한 값에서 변경이 되지 않았을 경우 만들 수 없는 경우로 -1을 반환하고 그렇지 않다면 해당 인덱스에 들어있는 최소 동전 개수를 반환한다.  

coins = [1, 2, 5] amount = 11

for (1 : coins) {
    for(1 : 11){
        dp[1] = Math.min(12, dp[0] + 1) = Math.min(12, 1) = 1
        dp[2] = Math.min(12, dp[1] + 1) = Math.min(12, 2) = 2
        .
        .
        .
        dp[11] = Math.min(12, dp[10] + 1) = Math.min(12, 11) = 11
    }
    
    for(2 : 11){
        dp[2] = Math.min(2, dp[0] + 1) = Math.min(2, 1) = 1
        dp[3] = Math.min(3, dp[1] + 1) = Math.min(3, 2) = 2
        .
        .
        .
        dp[11] = Math.min(11, dp[9] + 1) = Math.min(11, 6) = 6
    }
    
    for(5 : 11){
        dp[5] = Math.min(3, dp[0] + 1) = Math.min(3, 1) = 1
        dp[6] = Math.min(3, dp[1] + 1) = Math.min(3, 2) = 2
        .
        .
        .
        dp[11] = Math.min(6, dp[6] + 1) = Math.min(6, 3) = 3
    }
}

결과 : dp[11] = 3

흐름을 알아보기 편하게 정리한 것으로 해당 과정을 통해 dp 배열이 만들어진다. 

---

전체 코드

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
}

이 코드보다 실행 시간이 빠른 코드들이 존재하긴 했지만 Beats가 99.82% 인걸로 봐선 오로지 시간 단축을 위해 작성된 코드가 아닐까 싶다.

dp