LeetCode: 322번 (Coin Change) [JAVA]

문제 링크

https://leetcode.com/problems/coin-change/

Coin Change - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 amount 값 + 1만큼의 dp용 배열 전체 -1값으로 초기화, dp[0]의 경우 0으로, 그리고 주어진 coins 배열 속 값들을 인덱스로한 dp의 요소들은 1로 초기화
2. 재귀호출 기반으로 dp 함수를 작성. 인자는 coins 배열과 남은 돈의 양을 나타내는 remainAmount 값이며, 현재 남은 remainAmonut값에서 coins 배열을 돌며 뺀 값을 인덱스로 dp 값들 중 최소를 찾아 반환
3. 찾은 최소값 +1을 해당 dp 위치에 저장하며 반환
4. 해당 재귀호출 함수를 호출하고, 만약 결과가 불가능한 상황이면 -1반환, 그 외의 경우 해당 답 반환

 주어지는 인자가 coins 배열과 돈의 양을 나타내는 amount다 보니, 무작정 coins 배열 속 최대값부터 amount를 나누어가며 얻은 코인들의 개수의 합이 최소라고 생각할 수 있지만 그렇지 않다. 무조건 큰 coin들 많이 사용한다고 전체 코인 개수가 최소임을 보장하지 않기 때문에, 다른 방식으로 접근해야 한다.

 현재 amount의 최소 코인 개수를 찾으려면, 주어진 coins 배열 속 코인들의 값만큼 뺀 값들 속 최소 코인 개수를 찾으면 된다. 일종의 재귀함수를 활용하여 찾는 것으로, 구해진 최소 코인 개수 +1이 바로 현재 amount의 최소 코인 개수다. 여기에 dp를 적용하게 되면, 우선 주어진 amount값+1 길이의 dp용 배열을 전체 -1로 초기화한다. 그리고 dp[0]의 경우 0을, 주어진 coins 배열 속 값들을 인덱스로하는 dp 위치의 경우 1로 초기화한다. 이는 amount가 0이면 당연히 코인의 개수가 0이고, coins 값들에 딱 맞아 떨어지면 코인의 개수가 단 한 개면 되기 때문이다.

 그리고 재귀호출 함수를 작성하여, 인자는 coins 배열과 남은 돈의 양을 나타내는 remainAmount 값이며, 현재 남은 remainAmonut값에서 coins 배열을 돌며 뺀 값을 인덱스로 dp 값들 중 최소를 찾아 반환한다. 그리고 찾은 최소값 + 1을 해당 dp 위치에 저장하면서 반환한다. 그렇게 해당 함수를 호출해 결과값을 반환받는데, 만약 결과가 불가능한 상황이면 -1을, 그 외의 경우엔 해당 답을 반환한다.

 

class Solution {
    int[] dp;

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

        for (int i = 0; i < coins.length; i++) {//기존 coin 값과 동일한 amount는 1로 초기화
            if (coins[i] <= amount) {
                dp[coins[i]] = 1;
            }
        }

        answer = count(coins, amount);

        if (answer == 987654322) {//불가능한 상황인 경우
            return -1;
        } else {
            return answer;
        }
    }

    int count(int[] coins, int remainAmount) {
        int result = 987654321;

        if (dp[remainAmount] != -1) {//이미 계산된 값인 경우
            return dp[remainAmount];
        }

        for (int i = 0; i < coins.length; i++) {//현재 값에서 코인값만큼 뺀 값의 dp값들 중 최소값 찾기
            if (remainAmount - coins[i] >= 0) {
                result = Math.min(result, count(coins, remainAmount - coins[i]));
            }
        }

        return dp[remainAmount] = result + 1;//결과 + 1 저장
    }
}

결과