중복순열, DFS

✅ 여러 종류의 동전들이 주어졌을 때 가장 적은 수의 동전으로 거스름돈을 줄 수 있는 방법

동전 종류가 주어졌을 때 동전 최소 개수를 사용하여 거스름돈을 만들어 줄 수 있는 동전 개수를 구하세요.

//input
//동전 개수 종류
//동전 종류
//거스름돈
3
1 2 5
15
//output
3
//5 + 5 + 5

🟢 Code

class Main {
        static int n;
        static int m; //거스름돈
        static Integer[] coins; //동전 종류
        static int answer=Integer.MAX_VALUE;
        public void DFS(int L, int sum) {
            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+coins[i]);
                }
            }
        }

        public static void main(String[] args) {
            Main T = new Main();
            Scanner sc = new Scanner(System.in);
            n= sc.nextInt();
            coins= new Integer[n];
            for(int i=0; i<n; i++){
                coins[i]=sc.nextInt();
            }
            Arrays.sort(coins, Collections.reverseOrder()); //내림차순 정렬
            m= sc.nextInt();

            T.DFS(0, 0);
            System.out.print(answer);
        }
}

1. static int m = 거스름돈
   
2. static int[] coins = 동전 종류
   
3. ⭐️ static int answer=Integer.MAX_VALUE
   처음에 answer에 Integer.MAX_VALUE를 주지 않고
   static int answer; 로만 코드를 짰었다.
   그랬더니 answer는 0으로 초기화되었을 것이다.
   그래서 출력이 계속 0이 되었다. 0이 최소값이었을 것이기 때문이다.
   따라서 우리는 지금 동전 최소 개수를 구하는 것이므로 answer에다가 엄청 큰 값을 넣어줘야 올바르게 답을 출력할 수 있다.
   
4. if(sum>m) return;
   총합이 거스름돈보다 커지면 이 가지에는 답이 없다는 것이므로 멈추도록 하는 코드.
   이 코드가 없으면 무한 루프를 돌게 된다.
   
5. ⭐️ if(L>= answer) return;
   그림에서처럼, 만약 D(5, 15) 레벨 5에서 15라는 거스름돈 줄 방법을 찾았다면,
   그보다 더 깊이 있는 레벨 6, 7, ....15는 볼 필요가 없다!
   어짜피 우리는 최소값을 구하니까.
   그래서 더 큰 레벨은 보지 않도록 하는 코드를 추가한다.
   이렇게 코드를 추가하여 ⭐️시간 복잡도⭐️를 확 줄일 수 있다.
   

6. ⭐️ Arrays.sort(coins, Collections.reverseOrder());
   동전 종류 배열을 5, 2, 1순으로 정렬한다.
   왜냐하면 5인 동전으로 거스름돈을 줄 수 있는 경우를 찾아야지 더 빨리 최소 동전 개수를 찾으니까!
   만약 이 코드가 없으면 time limit 에러가 난다.
   
   배열을 뒤집기 위해서 사용하는 코드는 Collections.reverseOrder()인데,
   이 코드를 사용하기 위해서는 배열이 object이어야 한다.
   따라서 int❌ Integer⭕️로 바꿔주기
   

   

🟢 빼기 방식으로 풀기

class Main {
    static int n;
    static int m;
    static Integer[] coins;
    static int answer=Integer.MAX_VALUE;
    public void DFS(int L, int moneyLeft) {
        if(moneyLeft<0) return; //거스름돈에서 사용한 동전 빼다가 0보다 작아지면 return
        if(L>= answer) return;
        if(moneyLeft==0) answer= Math.min(answer, L); //0되면 거스름돈 줄 수 있다는 뜻이니 최소값 구하기
        else{
            for(int i=0; i<n; i++){
                DFS(L+1, moneyLeft-coins[i]); //기존 거스름돈에서 사용한 동전 빼기
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        n= sc.nextInt();
        coins= new Integer[n];
        for(int i=0; i<n; i++){
            coins[i]=sc.nextInt();
        }
        Arrays.sort(coins, Collections.reverseOrder());

        m= sc.nextInt();
        int moneyLeft=m;
        T.DFS(0, moneyLeft);

        System.out.print(answer);
    }
}