[220807][Tany][인프런](8-5) 동전교환

[juni8453]

📌 문제

• 문제

⭐️ 아이디어

• 편리한 완전 탐색을 위해 DFS 알고리즘 적용

🤔 고민한 내용

• DFS 재귀 부분에서 탈출 및 확인 부분과 DFS 함수 재귀 호출부분을 어떻게 설정해줘야 할까 ?
• 앞선 문제들과 다르게 각 인덱스를 무조건 더하는 경우의 수 밖에 없으므로 DFS 호출 부분은 하나로 !
• 3개의 TC 는 통과하는데 2개의 TC 에서 시간초과가 난다.. ?

💪 새롭게 배운 내용

• 새롭게 배웠다기 보단 이제야 어느정도 적응이 되는 느낌이다.

🆘 이해가 어려운 내용

❌ 해결하지 못한 이유

• 시간 초과의 해결법을 찾지 못해서 강의를 봤는데, 생각보다 간단한 아이디어로 해결했다.
• 입력에 따라 categories 배열은 작은 동전 값 부터 순서대로 정렬되는데, 이를 거꾸로 바꿔주기만 하면 된다.
• 즉, 큰 동전부터 작은 동전 순으로 찾아내야 시간 복잡도를 줄일 수 있는 것.

✅ 본인 풀이

⏱ 걸린시간 : 1965ms | 💾 메모리 : 26MB (실패 코드) ⏱ 걸린시간 : 129ms | 💾 메모리 : 26MB (성공 코드)

정답 코드
package study.section8;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Section0805 {
    static int answerCount = Integer.MAX_VALUE;
    static int changeMoney = 0;
    static Integer[] categories;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        categories = new Integer[n];

        for (int i = 0; i < categories.length; i++) {
            categories[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(categories, Collections.reverseOrder());

        changeMoney = Integer.parseInt(br.readLine());

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

    // 재귀 함수를 호출하며 거슬러줘야하는 금액과 재귀의 합이 같을 때
    // answerCount 의 값과 depth 를 비교하여 더 작은 값으로 교체
    private static void DFS(int depth, int sum) {

        // 계산할 필요가 없는 부분 체크 후 바로 탈출하도록 설정
        if (sum > changeMoney) return;
        if (depth > answerCount) return;

        // 탈출 구간 및 판단 구간 설정
        // 노드를 거치면서 생기는 합이 거슬러줘야 하는 값과 같다면 판단
        // depth 자체가 이전 노드의 거슬러줄 떄 필요한 동전 갯수
        if (sum == changeMoney) {
            answerCount = Math.min(answerCount, depth);
        // 재귀 함수 동작 구간 설정
        } else {
            for (int i=0; i< categories.length; i++) {
                // 각 원소를 더하는 경우의 수 밖에 없으므로 재귀 호출 부분은 하나
                // 대신 배열을 돌면서 하나 씩 더해야 하기 때문에 for 문 사용
                DFS(depth + 1, sum + categories[i]);
            }
        }
    }
}

참고한 자료

• 링크