[Algorithm] 동전 교환(DFS)

설명

여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해 줄 수 있는 최소 개수를 구하라.

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

 

입력

첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고,

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

 

출력

첫 번째 줄에 거슬러 줄 동전의 최소 개수를 출력한다.

 

예시 입력 / 출력

3 1 2 5 15

3

 

 

---

 

문제 과정.

1. 입력받은 동전들을 역순으로 정렬하여 재귀함수를 호출하게 만든다. (내림차순)

- 오름차순으로 진행할 경우 time limit exceeded 발생

- 내림차순으로 큰 동전부터 처리해야 시간복잡도가 많이 줄어든다

예를들어 위의 예시 입력 기준으로 오름차순 진행할 경우 거스름돈이 15, 동전의 종류 1부터 시작하여 처음부터

level15 까지 재귀함수를 호출하여 (백 트래킹 -> 함수호출) 반복으로 진행 되지만

내림차순으로 진행할 경우 거스름돈이 15, 동전의 종류 5부터 시작하여 level3 에서 거스름값을 만들게 되고 그 이상의 level은 조건에서 return하면 불필요한 재귀함수를 호출하지 않고 시간복잡도를 대폭 줄일 수 있다.

* 여기서 level은 동전의 갯수로 생각한다.

 

2. Collections.reverseOrder 사용하기 위해서는 정렬하고자 하는 배열이 int[](기본타입)이 아닌 Integer[](객체타입)으로 선언해줘야한다.

 

풀이.

public class Main {
    static int n; // 동전의 종류 갯수
    static Integer[] arr; // 동전의 종류 배열
    static int m; // 거스름 금액
    static int result = Integer.MAX_VALUE;

    static void DFS(int level, int sum){
        if(sum > m) return; // 거스름돈이 초과하면 return
        // level이 같거나 초과하면 return (이미 최솟값을 구한 상태)
        if(level >= result) return;
        if(sum == m){ // 금액의 합계(sum)과 거스름 금액이 같으면 참
            // 기존 구해놓은 result(level)과 현재level의 작은값을 대입
            result = Integer.min(result,level);
            return;
        }else{
            for (int i = 0; i < n; i++) {
                // 다음 level과 동전의 종류 배열값을 가지고 호출
                DFS(level+1,sum+arr[i]);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 동전의 종류 갯수
        arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt(); // n개의 동전의 종류
        }
        Arrays.sort(arr,Collections.reverseOrder());
        m = sc.nextInt(); // 거슬러 줄 금액
        DFS(0,0);
        System.out.println(result);
    }
}

 

 

 

 

---

정리 :

시간복잡도 신경쓰자..