05. 동전교환

가장 적은 수의 동전으로 교환

 

3

1 2 5

15

 

 

Integer배열을 내림차순으로 정렬하고 싶다면

=> Arrays.sort(arr, Collections.reverseOrder());

 

L이 answer보다 크다면 return

sum>m 보다 커도 return

 

 

 

import java.util.*;
class Main {
	static int n, m;
	static Integer[] arr;
	static int answer=Integer.MAX_VALUE;
	
	public void DFS(int L, int sum) {
		if(L>answer) {
			return;
		}
		if(sum>m) {
			return;
		}
		if(sum==m) {
			answer=Math.min(answer, L);
		}else {
			for(int i=0; i<n; i++) {
				DFS(L+1, sum+arr[i]);
			}
		}
	}
	
	
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		arr= new Integer[n];
		for(int i=0; i<n; i++) {
			arr[i]=kb.nextInt();
		}
		Arrays.sort(arr,Collections.reverseOrder());
		m=kb.nextInt();
	
		T.DFS(0,0);
		
		System.out.println(answer);
	}	
}