동전교환

설명

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

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

 

입력

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

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

 

출력

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

 

예시 입력 1 

3
1 2 5
15

 

예시 출력 1

3

 

힌트

출력 설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.

 

 

문제 해결

 

이 문제는 동전의 종류와 각각의 동전을 무한히 사용할 수 있을 때, 주어진 금액을 만들기 위해 필요한 최소 동전 수를 계산하는 문제이다.

 

static int N, M;
static int[] money;
static int[] minCoins; // M원을 만드는 데 필요한 최소 동전 수 배열
static int MAX = 100;

 

N은 동전의 종류 수이고, M은 만들어야 하는 금액, money 배열은 각 동전의 종류를 저장하고 , minCoins 배열은 M원까지  금액을 만드는 데 필요한 최소 동전 수를 저장한다. 거슬러 줄 동전의 최소 개수를 출력해야하므로  MAX를 크게 설정해둔다.

 

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    N = in.nextInt();
    money = new int[N];

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

    M = in.nextInt();
    minCoins = new int[M + 1];

    // 최소 동전 수 배열을 큰 값으로 초기화
    for (int i = 1; i <= M; i++) {
        minCoins[i] = MAX;
    }
    minCoins[0] = 0;  // 0원을 만드는 데는 동전이 0개 필요

    BFS();

    if (minCoins[M] == MAX) {
        System.out.println(-1);  // M원을 만들 수 없는 경우 -1
    } else {
        System.out.println(minCoins[M]);  // M원을 만드는 데 필요한 최소 동전 수
    }
}

• minCoins 배열을 MAX으로 초기화하여 모든 금액에 대한 최소 동전 수를 무한대로 설정하고 M을 만드는 데 동전이 하나도 필요 없는 경우 즉 0원은 0으로 설정한다.
• 만약 M원을 만드는 데 필요한 동전 수가 MAX와 같다면, -1을 출력하여 M원을 만드는 것이 불가능함을 출력하고
• 그렇지 않을 경우 M원을 만드는데 필요한 최소 동전 수를 출력한다.

 

public static void BFS() {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(0);

    //큐에서 하나씩 꺼내면서, 사용 가능한 모든 동전을 시도
    while (!queue.isEmpty()) {
        int current = queue.poll();

        for (int coin : money) {
            int next = current + coin; //각 동전을 현재 금액에 추가
            if (next <= M && minCoins[next] > minCoins[current] + 1) {//총액이 M을 초과하지 않고 이전에 찾은 최소 동전 수보다 적을 경우
                minCoins[next] = minCoins[current] + 1;  // 최소 동전 수 갱신
                queue.add(next); //큐에 추가
            }
        }
    }
}

 

• 큐에는 현재 금액을 저장한다.
• 큐가 비어있지 않는 동안 큐에서 금액을 하나씩 꺼내면서, 사용 가능한 모든 동전을 시도하고
• 각 동전을 현재 금액에 추가했을 때의 총액을 계산하고, 이 총액이 목표 금액 M을 초과하지 않으며 이전에 찾은 최소 동전 수보다 적을 경우에만 큐에 추가한다. (==> 더 적은 동전으로 같은 금액을 만들 수 있는 새로운 방법이 있음을 의미)

 

최종 코드

 

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

public class P05_동전교환 {
    static int N, M;
    static int[] money;
    static int[] minCoins;
    static int MAX = 100;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        money = new int[N];

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

        M = in.nextInt();
        minCoins = new int[M + 1];  // 각 금액에 도달하는데 필요한 최소 동전 수 배열

        // 최소 동전 수 배열을 큰 값으로 초기화
        for (int i = 1; i <= M; i++) {
            minCoins[i] = MAX;
        }
        minCoins[0] = 0;  // 0원을 만드는 데는 동전이 0개 필요

        BFS();
        System.out.println(minCoins[M] == MAX ? -1 : minCoins[M]);  // M원을 만들 수 없으면 -1 출력
    }

    public static void BFS() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);  // 0원부터 시작

        while (!queue.isEmpty()) {
            int current = queue.poll();

            for (int coin : money) {
                int next = current + coin;
                if (next <= M && minCoins[next] > minCoins[current] + 1) {
                    minCoins[next] = minCoins[current] + 1;  // 최소 동전 수 갱신
                    queue.add(next);
                }
            }
        }
    }
}