20240324 DFS

동전교환

 

package org.example.infrenJavaCodingTest;

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

public class chap9_5 {
    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) {
        chap9_5 T = new chap9_5();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        //int[] arr = new int[n];
        // Collections 사용을 위해서는 객체형 int 로 사용
        Integer[] arr = new Integer[n];
        for(int i=0; i<n; i++) arr[i] = kb.nextInt();
        // 거스름돈이 작은 수 부터 DFS 실행시 시간초과 에러 -> 큰 돈부터 계산을 위해 배열 정렬하기
        Arrays.sort(arr, Collections.reverseOrder());

        m = kb.nextInt(); // 거슬러 줄 금액
        T.DFS(0,0,arr);
        System.out.println(answer);
    }
}

 

그리디 문제로도 해결 가능. DFS 사용 시에는 동전을 큰 순서로 정렬해야 시간초과 에러가 나지 않는다.

일례로, 1원짜리 동전을 15번 사용하는 경우의 수는, DFS를 15번 호출하므로, 5원짜리 3번을 호출하는 것에 앞에 올 경우 시간 초과 에러가 발생한다.

 

순열

package org.example.infrenJavaCodingTest;

import java.util.Scanner;

// 순열 만들기
// 한번씩만 사용
public class chap9_6 {
    static int n,m;
    static int[] pm,ch,arr;
    public void DFS(int L){
        if(L==m){
            for(int x : pm) System.out.print(x+" ");
            System.out.println();
        }else{
            for(int i=0; i<n; i++){
                if(ch[i] == 0){
                    ch[i] = 1;
                    pm[L] = arr[i];
                    DFS(L+1);
                    ch[i] = 0;
                }
            }
        }
    }
    public static void main(String[] args) {
        chap9_6 T = new chap9_6();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        arr = new int[n];
        for(int i=0; i<n; i++) arr[i] = kb.nextInt();
        ch = new int[n];
        pm = new int[m];
        T.DFS(0);
    }
}

 

순열 : DFS + check배열

-> 순열은 원소 한번씩만 사용하므로, DFS 를 돌때 사용한 원소에 대한 체크가 필요

중복순열 : DFS

-> 중복순열은 원소를 중복하여 사용가능하므로 , 따로 check 배열이 필요 없다