동전교환 (DFS)

1. DFS(Level, sum) 형태로 해결

- 동전 종류만큼 N개 노드 생성

- level은 동전의 갯수, sum은 총액이 된다.

2. 최적화를 위해 단위가 큰 동전부터 탐색(노드를 생성)한다.

//아래 조건의 하위노드 생성하지 않음.
if ( sum > m || level >= min) return;

//만족하는 level 중 최소 값을 찾는다.
if ( sum == m) {
min = Math.min(min, level);
}

 

class Main {

	static int m, n;				
    //level의 최소값 찾기
	static int answer;
	static int min=Integer.MAX_VALUE;
	public void DFS( int level, int sum, int [] coin) {
		
		//아래 조건의 하위노드 생성하지 않음.
		if ( sum > m || level >= min) return;
		
		//만족하는 level 중 최소 값을 찾는다.
		if ( sum == m) {				
			min = Math.min(min, level);			
		} else {
			//코인의 갯수만큼 노드 생성, 큰 동전부터 탐색한다.
			for ( int i = n-1 ; i >=0 ; --i) {
				DFS(level + 1 , sum + coin[i],  coin);
			}
			
		}
		
	}
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		int coin[] = new int[n];
		for ( int i = 0 ; i < n ; i++)
			coin[i] = in.nextInt();
		
		m = in.nextInt();
		
		M.DFS(0, 0, coin);
		System.out.println(min);
	}

}

ex)
input
3
1 2 5
15
output
3