동전교환 (냅색)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class Main {

	static int m, n, answer;
	static int []dy;

	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);

		n = in.nextInt();
		int []coin = new int[n];
		for ( int i = 0 ; i<n ; i++) {
			coin[i] = in.nextInt();
		}
		m = in.nextInt();
		//dy[i]정의 :  i 금액을 만드는데 드는 최소 동전개수
		//dy[i]는 Integer.MAX로 초기화
		// dy[j] = dy[j - coin[i]] +1         
		dy = new int[m+1];
		
		Arrays.fill(dy, Integer.MAX_VALUE);
		dy[0] = 0;
		for ( int i = 0; i < n; i++) {
			for ( int j = coin[i]; j<=m ; j++) {
				dy[j] = Math.min(dy[j], dy[j - coin[i]]+1);
			}
		}
		
		System.out.println(dy[m]);

	}

}
ex)
input
3
1 2 5
15
output
3

동전교환표.xlsx

0.01MB