동전교환 (DFS)

import java.util.*;
// 중복순열이랑 비슷함
// DFS이나 가지수가 n개 일 때
class Main{
    static int n, m, answer = Integer.MAX_VALUE; // answer가 최소값이 되어야함.
    public void DFS(int L, int sum, Integer[] arr){ // 사용된 동전 개수, L개의 동전으로 만든 총합
        if(sum > m) return; // sum이 m값을 넘는 것을 방지
        if(L>= answer) return; // 현재 answer의 min값보다 더 탐색할 필요 없음
        if(sum == m) {
            answer = Math.min(answer, L);
        }else {
            for(int i=0; i<n; i++) { // 동전 다 사용하기 n가닥 뻗어나가기
               DFS(L+1, sum+arr[i], arr); 
            }
            
        }
    }
	public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        Integer[] arr = new Integer[n];
        for(int i=0; i<n; i++) {
            arr[i] = kb.nextInt();
        }
        // 거꾸로 큰금액부터하면 금방 연산이 끝남 내림차순으로 정렬하기
        // Collections.reverseOrder()를 하려면 기본형이 아니고 객체형 int로 바꾸자
        Arrays.sort(arr, Collections.reverseOrder() );
        m = kb.nextInt();
        T.DFS(0, 0, arr);
        System.out.println(answer);
        
	}
}