[문제풀이] 08-05. 동전 교환

인프런, 자바(Java) 알고리즘 문제풀이

DFS, BFS 활용 - 0802. 동전 교환(BFS, DFS)

---

🗒️ 문제

---

🎈 나의 풀이

	private static int BFS(int[] coins) {
        int answer = 0;
        int maxCoins = Arrays.stream(coins).max().getAsInt();
        Queue<Integer> Q = new LinkedList<>();
        Q.add(0);

        while(!Q.isEmpty()) {
            int len = Q.size();
            for(int i=0; i<len; i++) {
                int sum = Q.poll();
                if(change - maxCoins > sum) {
                    Q.add(sum + maxCoins);
                } else {
                    for(int j=0; j<coins.length; j++) {
                        if(sum + coins[j] == change) return ++answer;
                        if(sum + coins[j] < change) Q.add(sum + coins[j]);
                    }
                }
            }
            answer++;
        }

        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] coins = new int[n];

        for(int i=0; i<n; i++) coins[i] = sc.nextInt();

        change = sc.nextInt();

        System.out.println(BFS(coins));
    }

---

🖍️ 강의 풀이

  	static int n, m, answer=Integer.MAX_VALUE;
	public void DFS(int L, int sum, Integer[] arr){
		if(sum>m) return;
		if(L>=answer) return;
		if(sum==m){
			answer=Math.min(answer, L);
		}
		else{
			for(int i=0; i<n; i++){
				DFS(L+1, sum+arr[i], arr);
			}
		}	
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		Integer[] arr=new Integer[n];
		for(int i=0; i<n; i++) arr[i]=kb.nextInt();
		Arrays.sort(arr, Collections.reverseOrder());
		m=kb.nextInt();
		T.DFS(0, 0, arr);
		System.out.println(answer);
	}

---

💬 짚어가기

나의 풀이에서는 BFS를 이용하여 풀이하였다. 우선 동전 중 크기가 가장 큰 동전을
maxCoin에 저장하고, maxCoin의 누적액이 거스름돈을 넘지안는 동안의 최대
개수를 카운트하였다.

이후 남은 금액에 대해 너비 우선 탐색을 수행하였다. 각 동전을 더하여 구할 수 있는
모든 경우의 수를 확인하며, 최초로 거스름돈 금액이 등장하는 순간 카운트를 반환하여
문제를 해결하였다.

강의에서는 DFS를 이용하여 문제를 풀이하였다. 누적 액수를 파라미터로 전달 받고
반복문을 수행하며 누적 액수에 동전의 종류 별로 합산하여 다시 재귀 호출하는 방식으로
모든 경우의 수를 확인하였다.

📌 동전의 크기를 내림차순 정렬
DFS 탐색 전에 동전의 크기를 내림차순 정렬하였다. 깊이 우선 탐색이기 때문에 동전
배열의 가장 처음 동전을 시작으로 누적합하여 탐색하게 된다.

따라서 금액이 가장 큰 동전부터 탐색을 수행할 수 있도록 내림차순 정렬을 하게되면
BFS에서 초반에 가장 큰 금액의 동전만 이용한 것과 동일한 효과를 얻을 수 있다.