인프런 커뮤니티 질문&답변

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

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        List<Integer> coins = new ArrayList<>();
        for (int i=0; i<num; i++) {
            coins.add(in.nextInt());
        }

        int target = in.nextInt();

        in.close();

        Set<Integer> isVisited = new HashSet<>();
        Map<Integer, List<Integer>> countByCoins = new HashMap<>();

        for (Integer coin : coins) {
            if (coin == target) {
                System.out.print(1);
                return;
            } else {
                isVisited.add(coin);
            }
        }

        countByCoins.put(1, new ArrayList<Integer>(coins));

        int start = 2;
        while (true) {
            List<Integer> valuesByBefore = countByCoins.get(start - 1);
            List<Integer> newList = new ArrayList<>();
            for (Integer before : valuesByBefore) {
                for (Integer coin : coins) {
                    int sum = before + coin;
                    if (sum == target) {
                        System.out.print(start);
                        return;
                    }

                    if (!isVisited.contains(sum)) {
                        isVisited.add(sum);
                        newList.add(sum);
                    }
                }
            }
            countByCoins.put(start, newList);
            start++;
            // System.out.println(countByCoins);
        }
    }
}