동전교환 (DFS)

첫 번째 줄에 동전 종류의 개수 n

두 번째 줄에 동전의 종류가 n개
세 번째 줄에 거슬러 줄 돈 change가 주어질 때

거슬러 줄 동전이 최소가 되는 개수를 출력하라.

intput)

3

1 3 5

15

 

output)
3

import java.util.*;
  
public class Main {
  static int n, change, min = Integer.MAX_VALUE;
  static int[] arr;
  
  private static void solution(int cnt, int change) {
    if (min < cnt) return;
    
    if (change == 0) {
      min = Math.min(min, cnt);
      return;
    }
    
    for (int i = n - 1; i >= 0; i--) {
    	if (change >= arr[i]) {
          	// 동전을 사용한다. (사용한 동전의 개수 1 증가, 잔액을 해당 동전만큼 차감)
        	solution(cnt + 1, change - arr[i]);
        }
    }
  }
  
  public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    n = in.nextInt();
		arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = in.nextInt();
    }
    change = in.nextInt();
    
    Arrays.sort(arr);
    
    solution(0, change);
    
    System.out.println(min);
  }
}