[JAVA] 알고리즘 : 동적 계획법- 동전교환(냅색 알고리즘)

import java.util.Arrays;
import java.util.Scanner;

public class Main{
    static int n, m;
    static int[] dp;
    public int solution(int[] coin){
        Arrays.fill(dp, Integer.MAX_VALUE); // 큰 값으로 초기화
        dp[0] = 0;
        for(int i=0; i<n; i++){
            for(int j=coin[i]; j<=m; j++){ // 동전의 금액부터 거슬러줄 금액까지 증가
                dp[j] = Math.min(dp[j], dp[j-coin[i]]+1); // 더 큰 값의 동전으로 대체 할 수 있는지 비교
            }
        }
        return dp[m];
    }
    public static void main(String[] args) {

        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt(); // 동전의 개수
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = kb.nextInt();
        }
        m = kb.nextInt(); // 거슬러줄 금액
        dp = new int[m+1]; // dp[i] = 거슬러줄 금액 i를 만드는데 드는 최소 동전 개수
        System.out.println(T.solution(arr));
    }
}