[JAVA] 알고리즘 : DFS- 동전 교환

 

 

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

class Main{
    static int n, m, answer=Integer.MAX_VALUE;
    public void DFS(int L, int sum, Integer[] arr){
        if(sum>m) return; // 합이 거슬러 줄 금액을 넘으면 리턴
        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], arr);
            }
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt(); // 동전의 종류 개수
        Integer[] arr = new Integer[n];
        for(int i=0; i<n; i++) arr[i] = kb.nextInt();
        Arrays.sort(arr, Collections.reverseOrder());
        m=kb.nextInt(); // 거슬러 줄 금액
        T.DFS(0, 0, arr);
        System.out.println(answer);
    }
}

 

동전의 개수 L을 증가시키고 동전의 합을 누적시키며 dfs 함수를 재귀 호출한다.

동전의 합이 거슬러 줘야 하는 금액과 같아질때의 동전의 개수의 최솟값을 구한다. 

이 때 동전의 합이 거슬러 줘야 할 금액 m을 넘어버리거나 탐색하고자 하는 동전의 개수가 구해놓은 동전의 개수의 최솟값보다 커지면 더이상 탐색할 필요 없으므로 리턴시킨다. 

 

배열을 내림차순으로 정렬한 이유는 큰 값 부터 탐색해 더 빠르게 정답을 찾기 위함이다.