동전교환 (냅색 알고리즘)

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

public class Main {
	//냅색 알고리즘

	static int n, m;
	static int[] coins; //동전 종류 목록
	static int[] dynamic; //최소 동전 개수
	
	public int solution() {
		dynamic[0] = 0;
		
		for(int i=0; i<n; i++) {
			for(int j=coins[i]; j<=m; j++) {
				dynamic[j] = Math.min(dynamic[j], dynamic[j-coins[i]]+1);
			}
		}
		
		return dynamic[m];
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		
		n = kb.nextInt();
		coins = new int[n];
		for(int i=0; i<n; i++) coins[i] = kb.nextInt();
		m = kb.nextInt();
		dynamic = new int[m+1];
		Arrays.fill(dynamic, Integer.MAX_VALUE);
		
		System.out.println(T.solution());
	}

}