[Algorithm] 바둑이 승차(DFS)

설명

트럭은 C킬로그램 넘게 태울수가 없다.

C를 넘지 않으면서 바둑이들을 가장 무겁게 태우고 싶다.

N마리의 바둑이와 각 바둑이의 무게 W가 주어지면,

트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.

 

입력

첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다.

둘째 줄부터 N마리 바둑이의 무게가 주어진다.

 

출력

첫 번째 줄에 가장 무거운 무게를 출력한다.

 

예시 입력 / 출력

259 5 81 58 42 33 61

242

 

---

 

풀이.

public class Main {
    static int c; // 최대 허용 킬로그램
    static int n; // 바둑이 마릿수
    static int[] arr; // 바둑이들의 무게 배열
    static int result = 0; // 출력할 결과 값
    
    static void DFS(int level,int sum){
        // 현재 DFS함수 까지의 바둑이들의 누적 무게(sum)이 최대 허용(c)보다 크면
        // 더 이상 아래로 뻗어 나갈 필요 없이 return
        if(sum > c) return;
        // c보다 같거나 작은 sum을 가지고 마지막 레벨에 도착 하면 조건을 태운다.
        if(level == n){
            if(result < sum){ // 현재의 결과 값보다 크면 담는다.
                result = sum;
                return;
            }
        }else{
            DFS(level+1,sum+arr[level]); // 현재 무게를 누적하고 다음 level로 간다.
            DFS(level+1,sum); // 기존 무게를 가지고 다음 level로 간다.
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        c = sc.nextInt();
        n = sc.nextInt();
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        DFS(0,0); // Level = 0, sum = 0으로 시작 (root노드를 level 1로 설정)
        System.out.println(result);
    }
}

 

---

 

정리 :

처음 트리로 구상 할 때 약 원소가 10개일 경우 포함시킬지(O), 포함시키지 않을지(X) 경우의 수가 10x2=20이다.

즉 간선의수 = 20이 되고 level은 1로 설정시 최대 level = 10