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

동전교환 문제 풀이 좀 더 개선이 가능할까요??

입력이
3

1 2 3

500

이라고 할 때 재귀가 많이 호출되서? 답을 찾을 기미가 안보이는데요.

혹시 DFS 방식으로 이 문제 개선이 가능한가요??

강의를 안보고 약간 무식한 BFS 방식으로 풀었을 때 정답 통과되고 위 문제도 해결은 가능한데 이런 종류의 문제 풀 때 DFS 방식으로 푸는게 맞는지 궁금합니다.

질문이 길어졌습니다(_)(_)

- BFS

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

public class Main {

    public static int n;
    public static int m;
    public static int[] chk = new int[501];

    public int BFS(int idx, int[] arr) {
        LinkedList<Integer> Q = new LinkedList<>();
        Q.offer(arr[idx]);
        int L = 1;
        while (!Q.isEmpty()) {
            int len = Q.size();
            for (int i = 0; i < len; i++) {
                int k = Q.poll();
                if (k == m) return L;
                for (int j = 0; j < n; j++) {
                    int x = arr[j] + k;
                    if (x == m) return L + 1;
                    if (x <= 500 && chk[x] == 0) {
                        Q.offer(x);
                        chk[x] = 1;
                    }
                }
            }

            L++;
        }

        return Integer.MAX_VALUE;
    }

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

        Main T = new Main();
        int answer = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            answer = Math.min(T.BFS(i, arr), answer);
            chk = new int[501];
        }

        System.out.print(answer);
    }
}