[코딩 테스트] 동전 교환 (BFS)

문제

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

▣ 입력설명

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

▣ 출력설명

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

▣ 입력예제 1

3
1 2 5
15

▣ 출력예제 1

3

생각

• 가장 적은 숫자의 동전을 사용하려면 값이 많이 나가는 동전부터 검사하는 것이 시간 복잡도를 낮춰줄 것이라고 생각했다!
• 동전 수의 최솟값 = L (level)의 최솟값을 구하는 것이므로 BFS를 사용
• 동전들의 누적합이 M인지 아닌지 확인해야 하므로 동전 수의 최솟값 뿐만 아니라 누적합까지 Queue에 담아 확인하였다
• 합이 M을 초과하는 경우 더 이상 탐색할 필요가 없기에 continue; 를 사용하여 탐색을 스킵하여 시간 복잡도를 더 줄이고자 했다

코드

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

public class ExchangeCoin {

    public static int N;
    public static int M;
    public static Integer[] type;
    public static Queue<int[]> Q = new LinkedList<>();

    public int BFS() {

        Q.offer(new int[] { 0, 0 });

        while (!Q.isEmpty()) {
            int[] current = Q.poll();
            int sum = current[0];
            int L = current[1];
            
            if (sum > M)
                continue;
            if (sum == M)
                return L;

            for (int t : type) {
                int nextSum = sum + t;
                if (nextSum <= M) {
                    Q.offer(new int[] { nextSum, L + 1 });
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        ExchangeCoin T = new ExchangeCoin();
        Scanner kb = new Scanner(System.in);

        N = kb.nextInt();
        type = new Integer[N];

        for (int i = 0; i < N; i++) {
            type[i] = kb.nextInt();
        }

        Arrays.sort(type, Collections.reverseOrder());

        M = kb.nextInt();
        System.out.println(T.BFS());
        kb.close();
    }

}

정리

• sum 이 M을 초과할 때, continue로 탐색을 skip하기만 해도, 시간을 상당히(2배 이상) 단축 시킬 수 있었다!

• 위: continue 사용/아래: continue 미사용
  

• 이래서 코드를 짤 때 불필요한 코드나 잘못된 범위를 탐색하고 있지는 않은지 항상 검토해봐야 하는 것 같다

• 간단 내림차순 정렬 방법

  • int[] 타입이 아닌 Integer[] 타입임을 기억하자

  type = new Integer[N];
  Arrays.sort(type, Collections.reverseOrder());

문제 출처