8-5. 동전교환 (DFS)

---

 

 

문제

 

 

 

 

 

순서도

 

 

 

큰수부터 하는게 경우의 수를 줄일 수 있음으로 역순으로 트리를 타게했다.

keypoint : 동전의 수를 구했을때, 그보다 큰 동전의 수를 가지고 있는 메소드(재귀)를 더 이상 진행할 필요가 없다.

이부분 에서 시간의 차이가 매우 크게 난다. 

 

 

소스

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

//백준
public class Main {

	static int[] array;
	static int size;
	static int money;
	static int count = Integer.MAX_VALUE;

	public static void dfs(int cnt, int sum) {

		if(cnt>=count) return;
		if(money < sum ) return;
		
		if (sum == money) {
			if (count > cnt) {
				count = cnt;
			}
		} else{

			
			for(int i=size-1; i>=0; i--) {
			dfs(cnt+1, sum+ array[i]);
			}

		}
	}

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// Queue<Integer> q = new LinkedList<>();

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		size = Integer.parseInt(st.nextToken());
		array = new int[size];

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < size; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(array);

		money = Integer.parseInt(br.readLine());

		dfs(0, 0);
		System.out.println(count);

	}

}