[PS] 인프런 강의 - DFS 5. 동전교환

 

문제

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환
해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

▣ 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다. 각 동전의 종류는 100원을 넘지 않는다.

 

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

 

▣ 입력예제 1
3
1 2 5
15

 

▣ 출력예제 1
3

 

설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.

 

풀이

 

DFS(L: 사용된 동전의 개수, sum: 합계) 로 푼다.

 

합계 sum이 거슬러줄 금액 m보다 크면 리턴하고 트리를 거슬러 올라가고

sum==m이면, L을 최소값과 비교한 뒤 작은 값을 최소값변수(answer)에 저장한다.

(거슬러 줄 동전의 최소 개수를 구해야 하므로 answer에는 큰값인 Integer.MAX_VALUE를 넣어둔다)

→ 이 부분을 자꾸 빠뜨려서 큰일이다 ㅠㅠ

 

풀기 쉬운 것 같으면서도, 시간 제한이 있다면 시간 복잡도 줄이는 법을 알아야 해서 새로웠다.

 

* 시간 복잡도 줄이는 법 *

동전 1, 2, 5 순서로 트리를 뻗는다고 하면

 

최초에는 D(15,15)가 answer에 들어가고, 그 다음에 오는  D(3,15)가  동전 개수가 적기때문에 answer값이 변경되는데,

 

동전 최소 개수를 구하는 거기 때문에 L=5 이하로 내려갈 필요가 없다. 여기서 커트쳐줘야 시간 복잡도를 확 줄일 수 있다.

 

그리고 동전 종류가 저장된 배열을 내림차순 정렬을 해서 큰 금액부터 트리를 뻗어나가면 시간을 줄일 수 있다. (5 2 1)

 

Arrays.sort(coin, Collections.reverseOrder());//내림차순 정렬

 

그런데 이렇게 Collections를 사용해서 정렬을 할 경우, 대상 변수가 int가 아닌 Integer 타입이어야 한다. 

 

 

그러면 이런 트리가 된다!

 

코드

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

public class Main {
	
	static Integer n, m;
	static Integer[] coin;
	static int answer= Integer.MAX_VALUE; //주의! 최소값 구해야 해서 큰값 넣음
	
	//L : 동전개수, sum: 합계
	public static void DFS(int L, int sum) {
		if(sum > m || L >= answer) return;
		if(sum == m) {
			//주의!! 같은 개수에서 답이 여러개인 경우 중 최소값 구하기
			answer = Math.min(answer, L); 
		}
		else {
			//코인 종류 순회
			for(int i=0; i<n; i++) {
				DFS(L+1, sum + coin[i]);
			}
		}
	}

	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        n = in.nextInt(); //1~12 동전의 종류개수
        coin = new Integer[n];
        
        for(int i=0; i<n; i++) {
        	coin[i] = in.nextInt(); //100원 미만
        }
        Arrays.sort(coin, Collections.reverseOrder());//내림차순 정렬

        m = in.nextInt();//1~500 거슬러 줄 금액
        
        //거슬러 줄 동전의 최소개수
        DFS(0,0);
        System.out.print(answer);
        
    }
}