[LeetCode] Coin Change

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

 

문제 파악

-트리를 타고 내려가며 주어진 amount값을 최소한의 갯수로 채우기

-dfs를 활용한 그리디 알고리즘으로 해석

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

접근 방법

-(최적) 그리디 알고리즘

-(차선) 일단, 동전 금액이 큰 것부터 적용시켜야 유리하므로 정수 배열 내림차 순 정렬하기

-dfs함수 구현(total은 0에서 시작, 경우의 수에 따라 누적해가기 and backtrack())

-금액이 들어가면 리스트에 누적해가다가 total이 amount와 동일해지면 return,

그렇지 않으면 recursive 또 돌면서 total 누적해가기

코드 구현

(그리디)

import java.util.*;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[max];
        Arrays.fill(dp, max);
        dp[0] = 0;
        
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

(DFS)

import java.util.*;
class Solution {
    public int coinChange(int[] coins, int amount) {
        int n=coins.length;
        Integer[] coinsArr = new Integer[n];
        //int[] -> Integer[]
        for(int i=0;i<n;i++) coinsArr[i] = coins[i];
        Arrays.sort(coinsArr,Collections.reverseOrder());
        List<Integer> result = new ArrayList<>();
        dfs(coinsArr,amount,0,result);
        System.out.println(result.toString());
        if(result.size()==1) return -1;
        return result.size();
    }
    public void dfs(Integer[] coinsArr,int amount,int total,List<Integer> result){
        if(total==amount){
            System.out.println("total은"+total);
            return;
        }
        for(int i=0;i<coinsArr.length;i++){
            if(coinsArr[i]>amount) continue;
            if(coinsArr[i]<amount){
                if((total+coinsArr[i])>amount){
                    continue;
                }else if((total+coinsArr[i])<=amount){
                    result.add(coinsArr[i]);
                    dfs(coinsArr,amount,total+coinsArr[i],result);
                    return;
                }
            }
        }
    }
}

배우게 된 점

그리디를 이용한 풀이가 더 빠르다는 것을 알게되었다.