Q. (X)

---

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환
해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.
▣ 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종
류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
각 동전의 종류는 100원을 넘지 않는다.
▣ 출력설명
첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.
▣ 입력예제 1
3
1 2 5
15
▣ 출력예제 1
3
설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다

실패 요인

전략

• {5 5 5} -> 중복순열
• 트리 & 스택 그려보기
  

정답

import java.util.*;
class Main{
	static Integer[] arr;
	static int n, m;
	static int answer = Integer.MAX_VALUE;	// 동전 최소 개수
	// L은 사용된 동전 개수, sum은 L개의 동전의 총합
	public void DFS(int L, int sum){
		// 하나의 부분집합을 구성하는 경우의 수에서 영원히 m과 일치하는 sum이 나타나지 않을 경우가 대부분임
		// -> if(sum == m) 조건만으로는 무한 재귀에 빠질 수 있다.
		// -> if(sum>m) return; 필요
		if(sum>m) return;
		// 동전 개수 L이 현재 최소개수보다 크다면, 해당 L은 이미 최소 개수가 아님
		// -> 시간 복잡도를 줄일 수 있다.
		if(L>=answer) return;

		if(sum == m){
			answer = Math.min(answer, L);
		}else{
			for(int i=0; i<n; i++){
				DFS(L+1, sum+arr[i]);
			}
		}
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt(); // 동전 종류 수 
		arr=new Integer[n];
		for(int i=0; i<n; i++)arr[i]=kb.nextInt();
		// 큰 원소를 먼저 재귀 처리하면, 더 적은 동전 개수로 sum을 구성 할 수 있다. 
		// 만약 내림차순 하지않아 [1,2,5]일 경우 1+1+..+1 = 15가 먼저 구성되어 느리다.
		Arrays.sort(arr, Collections.reverseOrder());
		m = kb.nextInt(); // 거슬러줄 금액
		T.DFS(0, 0);
		System.out.println(answer);
	}
}