Coin Change

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

Coin Change - LeetCode

 

주어진 코인 종류로 목표 금액을 맞추기 위해 필요한 최소 개수를 구하는 문제이다. dp 문제로 어떻게 풀어낼지 고민하다가 에라토스테네스의 체 알고리즘이 떠올랐다. 해당 알고리즘은 소수를 구하는 알고리즘으로 소수들로 이루어질 수 있는 약수들을 하나씩 체에 거르는 식으로 지워가는 방법이다.

 

그와 마찬가지로 이 문제의 경우 코인의 종류 별로 이룰 수 있는 값들의 최소 개수를 dp 배열에 적어가며 업데이트 하며 문제를 해결해 나갔다. 작은 값부터 하여 dp[0]은 0인 값으로 코인 1개일 때의 값을 적절히 계산될 수 있도록 초기화 해준 이후 조건에서 제시한 최대 값을 기준으로 극한 값을 설정해주었다. 아래는 최종 코드이다.

import java.util.Arrays;  
  
public class Solution {  
    public int coinChange(int[] coins, int amount) {  
        Arrays.sort(coins);  
  
        int[] dp = new int[amount + 1];  
        int INF = 10001;  
        Arrays.fill(dp, INF);  
        dp[0] = 0;  
  
        for (int i = 0; i < coins.length; i++) {  
            int coin = coins[i];  
            for (int j = coin; j <= amount; j++) {  
                dp[j] = Math.min(dp[j - coin] + 1, dp[j]);  
            }  
        }  
  
  
        return dp[amount] == INF ? -1 : dp[amount];  
    }  
}