동전 교환

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?

각 단위의 동전은 무한정 쓸 수 있다.

 

입력

3
1 2 5
15

 

출력

3

 

dfs 기존까지 해오던 방식 + 최적화를 해야 하는 문제

 

배열을 내림차순으로 받기 위해서 Array.sort(arr, Collections.reverseOrder()) 형태로 정렬할때 배열은 int형이 아니라

Integer 객체 배열 형태로 받아줘야 한다.

 

입력받은 배열을 1, 2, 5 순서로 하면 dfs를 상당히 많이 해야 되서 오류가 나기에

배열을 뒤집어 sum에 큰 숫자부터 들어가게 만들어줬다, 그리고 구한 횟수보다 더 깊이 dfs가 들어가면 어차피 정답이 안되기에 더 많은 횟수로 dfs하는 것도 제외한다

 

import java.util.*;
import java.util.stream.Stream;


public class Main{
    static Integer[] arr;

    static int res, min = Integer.MAX_VALUE;

    public void dfs(int v, int sum){
        if (sum > res) return;
        // 지금까지 나와있는 값 보다 더많은 횟수로 가는 것은 볼 필요가 없음
        if (v >= min) return;
        if (sum == res) min = Math.min(min, v);
        else {
            for (int i = 0; i < arr.length; i++){
                dfs(v+1, sum + arr[i]);
            }
        }

    }

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

        int n = in.nextInt();
        arr = new Integer[n];
        for(int i = 0; i < n; i++) arr[i] = in.nextInt();
        Arrays.sort(arr, Collections.reverseOrder());

        res = in.nextInt();

        T.dfs(0, 0);
        System.out.println(min);

    }
}