동전 교환(BFS, Queue)

문제설명

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

입력 설명

• 첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다. 각 동전의 종류는 100원을 넘지 않는다.
  
  

출력 설명

• 첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

입력예제

3
1 2 5
15

출력예제

3

---

내 코드

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

public class Main_8_5_bfs {
    static int n;
    static int m;
    static int[] arr;
    int bfs(){
        Queue<Integer> q = new LinkedList<>();
        int lv = 1;
        q.offer(0);
        while(!q.isEmpty()){
            int len = q.size();
            for(int i = 0; i < len; i++){
                int cur = q.poll(); // 시작은 0
                for(int j =0; j < arr.length; j++){
                    int result = cur + arr[j];
                    if(result == m)
                        return lv;
                    q.offer(result);
                    result = 0;
                }
            }
            lv++;
        }
        return 0;
    }

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

        System.out.println(t.bfs());
    }
}

• BFS를 활용하여 풀어보았습니다.
• lv은 동전의 갯수를 의미하며 현재 큐에 들어가있는 숫자들이 for문을 통해 arr의 3개의 숫자들을 더하는 것을 반복하여 만약 입력 값인 15가 나온는 경우 lv를 return 합니다.