동전교환(DFS, BFS)

 

부분집합 문제와는 다르게 동전을 여러개 쓸 수 있다.

여기선 해당 인덱스의 동전을 사용한다. 라고 재귀호출

L == n 이 되면 모두 1원으로 바꾸어주는 것 ~ 5원으로 바꾸어주는 것에 대한 조합(?)들이 만들어진다.

★구해둔 동전의 갯수가 있을 때 그 갯수보다 많이 거슬러주는 부분을 찾아볼 필요가 없다.

 

BFS가 좀 더 맞는답.

 

1.DFS

import java.util.*;

public class Main {
    static int n, m, answer = Integer.MAX_VALUE;

    //L을 동전의 갯수,sum을 L개의 동전의 총합이라 생각
    public void DFS(int L, int sum, Integer[] arr) {
        //동전의 총합이 m보다 크면 만들 수 없음
        if(sum > m) return;
        //이미 구해둔 동전의 최소 갯수보다 같거나 더 많이 갯수를 탐색할 필요 없음
        if(L>=answer) return;
        if(sum == m) {
            answer = Math.min(answer, L);
        }
        else {
            for(int i = 0; i < n; i++) {
                //동전을 n가닥으로 계속 뻗어나가면서 찾아보기
                //동전을 사용한다.로 생각해도 됨★
                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);

    }

}

 

2.BFS

import java.util.*;

public class Main {
    static int n, m, answer;
    static int[] dis,ch;
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        dis = new int[n];
        ch = new int[501];
        for(int i = 0; i < n; i++) dis[i] = kb.nextInt();
        m = kb.nextInt();
        T.solution(1);
        System.out.println(answer);
    }

    private void solution(int L) {
        Queue<Integer> q = new LinkedList<>();
        //일단 동전들 큐에 넣어놓기
        for(int i = 0; i < n; i++) q.offer(dis[i]);

        while(!q.isEmpty()) {
            int len = q.size();
            System.out.println(q);
            //q사이즈 만큼돌기
            for(int i = 0; i < len; i++) {
                int won = q.poll();
                //동전의 갯수만큼 돌기
                for(int j = 0; j < dis.length; j++) {
                    int nextWon = won + dis[j];
                    if (nextWon == m) {
                        answer = L + 1;
                        return;
                    }
                    if(ch[nextWon] == 0 && nextWon <= 500) {
                        ch[nextWon] = 1;
                        q.offer(nextWon);
                    }
                }
            }
            L++;
        }
    }
}