[Algorithm]알고리즘 자바_58 동전 교환

 

💬 문제 설명

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

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

 

 

🔨 입출력 예

 

입력 - 첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다.

두 번째 줄에는 N개의 동전의 종류가 주어지고,

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

3
1 2 5
15

출력 - 첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다. (5 5 5 동전 3개로 거슬러 줄 수 있다.)

3

 

 

✨ 아이디어

​

DFS(Level, sum)으로 재귀를 진행, coins의 크기에 따라 DFS 가지의 수를 지정한다.

• 재귀 탈출 조건
  • sum이 거슬러 줄 금액을 넘으면 return
  • Level값이 answer보다 크거나 같으면 더 이상 볼필요가 없다.
    • 이미 최소 값이 구해졌기 때문
  • 최적의 답을 먼저 내기 위해서 내림차 순 coins를 정리하자.

 

 

💻 Solution.java

import java.util.*;

public class Main {
	static Integer[] coins;
	static int n, m;
	static int min = Integer.MAX_VALUE;
	
	public void DFS(int L, int sum) {
		if(sum > m) return;
		if(L >= min) return;
		if(sum == m) {
			min = Math.min(min, L);
		}
		else {
			for(int i = 0; i < n; i++) {
				DFS(L + 1, sum + coins[i]);
			}
		}
 	}
	
	public static void main(String[] args){
		Main main = new Main();
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt(); // 동전의 종류
		coins = new Integer[n];
		for(int i = 0; i < n; i++) 
			coins[i] = sc.nextInt();
		Arrays.sort(coins, Collections.reverseOrder());
		m = sc.nextInt(); // 거슬러 줄 금액
		
		main.DFS(0, 0);
		System.out.println(min);
		sc.close();
		return ;
	}
}