동전 교환

13 May 2023 in Algorithm on Java, Coding, Test

문제

설명

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

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

입력

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

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

출력

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

예시 입력 1

3
1 2 5
15

예시 출력 1

3

힌트

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

해결방법

• 중복 순열과 비슷하게 생각해야 함. 중복 허용하여 가지치기를 계속 나아가는 형태이므로 계속 반복을 돌려야 함.
• 마이너스를 신경쓰지 않기 위해, 받은 돈에서 체크한 걸 빼는게 아닌 더하는 변수 만들어서 비교함.
• 단, 시간상 효율을 위해 정렬 코드가 들어갔음. 원래는 좀 걸림.

코드

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

class Main {

    static int result = Integer.MAX_VALUE, count, money;


    public void DFS(int L, int sum, Integer[] coins) {
        // 거슬러준 돈의 합계가 돈보다 크다면 종료.
        if (sum > money) return;
        // 횟수가 초과된다면 종료.
        if (L >= result) return;
        // 합계와 거슬러 줄 돈이 같다면 최소 값을 구한다.
        if (sum == money) {
            result = Math.min(L, result);
        } else {
            // 반복하여 재귀호출한다.
            for (int i = 0; i < coins.length; i++) {
                DFS(L + 1, sum + coins[i], coins);
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        count = kb.nextInt();
        Integer[] coins = new Integer[count];
        for (int i = 0; i < count; i++) {
            coins[i] = kb.nextInt();
        }
        // 시간 단축을 위해 정렬하고 시작함.
        Arrays.sort(coins, Collections.reverseOrder());
        money = kb.nextInt();
        T.DFS(0, 0, coins);
        System.out.print(result);
    }
}