거스름돈이 가장 적은 동전

거스름돈이 가장 적은 동전

동전의 개수 N개
두번 째 줄에는 N개의 동전의 종류
거슬러줄 금액 M

ex)
3
1 2 5
15

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int n, m;
    static int[] coins;
    static Queue<Integer> queue = new LinkedList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        coins = new int[n];
        for (int i = 0; i < n; i++) {
            int value = scanner.nextInt();
            queue.offer(value);
            coins[i] = value;
        }
        m = scanner.nextInt();

        System.out.println(bfs());
    }

    private static int bfs() {

        int cnt = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            cnt++;
            for (int i = 0; i < size; i++) {
                Integer sum = queue.poll();
                for (int value : coins) {
                    sum += value;
                    if (sum == m) {
                        return cnt;
                    } else if (sum < m) {
                        queue.offer(sum);
                    }
                    sum -= value;
                }

            }
        }

        return 0;
    }


}