5. 동전교환

1. 문제

설명

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

각 단위의 동전은 무한정 쓸 수 있다.

입력

첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고,

그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.각 동전의 종류는 100원을 넘지 않는다.

출력

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

예시 입력 1 

3
1 2 5
15

예시 출력 1

3

 

2 - 1. 나의 풀이

최소 개수를 구하므로 BFS로 풀었다.

동전 종류개수와 금액이 적어서 별다른 조건없이 BFS로 돌려도 풀리는 듯 하다.

 

좀 복잡하게 풀어서 차후에 봐도 잘 모르겠다.

 

 

2 - 2. 나의 코드

package DFS_BFS_levelup;
import java.util.*;

public class dfs_05_myself {
    public static int n; //동전 종류의 개수
    public static int m; //거슬러 줄 금액
    public static int line; // (m/max) + (m%max)
    public static int min_count=Integer.MAX_VALUE;

    public static void BFS(Integer[] arr) {
        Queue<Node1> q = new LinkedList<>();
        q.add(new Node1(0,0));

        while (!q.isEmpty()) {
            Node1 tmp = q.poll();
            int SUM = tmp.sum;
            int COUNT = tmp.count;
             if(tmp.sum == m) {
                System.out.println(tmp.count);
                System.exit(0);
            }else{
                for (int i = 0; i < n; i++) {
                    q.offer(new Node1(SUM + arr[i], COUNT + 1));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
        Arrays.sort(arr, Collections.reverseOrder());
        m = sc.nextInt();

        BFS(arr);
        /*DFS(0, 0, arr);*/
        System.out.println(min_count);

    }
}

class Node1{
    int sum;
    int count;

    Node1(int sum, int count) {
        this.sum = sum;
        this.count = count;
    }
}

 

3 - 1. 강의 풀이

1. DFS로 문제 풀이

강의에서는 DFS로 문제를 풀었으나, 섹션 10에서 이 문제는 DP(냅색 알고리즘)으로 푼다고 한다.

즉, 단순 DFS 연습용이다.

 

2. DFS가 계속 뻗어나가는 걸 방지하기 위한 조건

• (1) sum > m 인 경우: 동전의 합이 주어진 m보다 커진 경우는 DFS를 뻗을 필요가 없다.
• (2) L > answer 인 경우: L은 동전의 개수, answer는 DFS를 돌렸을 때 결과 중 최소를 저장해둔 값이다. answer보다 낮은 값을 찾아 나가므로 L > answer인 경우는 고려하지 않는다.
• (3) sum == m 인 경우: answer = Math.min(answer, L); 로 최소값을 저장한다.

 

3. DFS를 효율적으로

DFS를 효율적으로 사용하기 위해서 동전을 저장한 배열 arr을 내림차순으로 정렬한다.

Arrays.sort(arr, Collections.reverseOrder());를 사용해 내림차순으로 정렬한다.

 

•  Arrays.sort(arr, Collections.reverseOrder()); 를 사용하기 위해서 배열 타입이 참조타입이어야 하므로 Integer배열을 사용해 저장한다.

 

 

3 - 2. 강의 코드

package DFS_BFS_levelup;
import java.util.*;

public class pratice_myself {
    public static int n,m;
    public static Integer[] arr;
    public static int answer = Integer.MAX_VALUE;
    public static void DFS(int L, int sum) {
        if(sum > m) return;
        if(L>= answer) return;
        if(sum == m){
            answer = Math.min(answer, L);
        }else if (sum < m){
            for (int i = 0; i < n; i++) {
                DFS(L + 1, sum + arr[i]);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new Integer[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
        m = sc.nextInt();
        Arrays.sort(arr, Collections.reverseOrder());
        DFS(0, 0);
        System.out.println(answer);
    }
}

 

4. 얻어갈 점

Arrays.sort(arr, Collections.reverseOrder()); 를 사용하기 위해서 배열 타입이 참조타입이어야 하므로 Integer배열을 사용해 저장한다.