동전 쌓기 (Knapsack)

거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게주면되는가

입력)
첫째 줄에 동전의 종류개수 N
두번째 줄에는 N개 동전의 종류
마지막 줄에 거슬러줄 금액 M

ex)
3
1 2 5
15

출력) 거슬러줄 동전의 최소의 개수를 출력
3

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    static int n, m;
    static Integer[] coins;

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

        Arrays.sort(coins, Collections.reverseOrder());

        System.out.println(knapsack(0, m));
    }

    private static int knapsack(int index, int sum) {
        if (index == n || sum == 0) {
            if(sum == 0)
                return 0;
            else
                return Integer.MAX_VALUE;
        } else {
            int count = sum / coins[index];
            int newSum = sum - count * coins[index];
            return Math.min(
                    knapsack(index + 1, sum),
                    count + knapsack(index + 1, newSum)
            );
        }
    }


}