[220808][BC][인프런](8-5) 동전교환

[honeySleepr]

📌 문제

• 문제

⭐️ 아이디어

• DFS를 사용한 완전 탐색

🤔 고민한 내용

💪 새롭게 배운 내용

• 모든 경우의 수를 다 도는 완전탐색을 DFS로 구현하는 방법

🆘 이해가 어려운 내용

❌ 해결하지 못한 이유

✅ 본인 풀이

public class P0805 {

    private static List<Integer> list = new ArrayList<>();
    private static int n;
    private static int target;
    private static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        String[] split = br.readLine().split("\\s");
        target = Integer.parseInt(br.readLine());

        /* 0 인덱스 채워줌. 어차피 안씀. sort 시에 꼬이지 않도록 최대값 입력 */
        list.add(Integer.MAX_VALUE);
        for (int i = 1; i < n + 1; i++) {
            list.add(Integer.parseInt(split[i - 1]));
        }
        /* 큰 수부터 해야 아무래도 최소값이 빨리 나올테니 */
        Collections.sort(list, Comparator.reverseOrder());

        DFS(0, 0);
        System.out.println(answer);
    }

    private static void DFS(int L, int sum) {

        if (sum > target || L > answer) {
            return;
        }
        if (sum == target) {
            answer = Math.min(answer, L);
            return;
        }
        for (int i = 1; i < n + 1; i++) {
            sum += list.get(i);
            DFS(L + 1, sum);
            sum -= list.get(i);
        }
    }
}

참고한 자료