바둑이 승차(DFS)

 

앞의 문제와 같이 부분집합 개념의 문제라고 볼 수 있다. - 이걸 생각해낼 줄 알아야함

여기선 해당 인덱스의 원소(바둑이의 무게)를 트럭에 태운다/태우지 않는다라고 재귀호출

L번째 인덱스에 있는 바둑이의 무게를 더한다/더하지않는다 인것!

L == n이 되면 바둑이들의 무게를 모두 더한것 ~ 모두 더하지 않는 것에 대한 조합(?)들이 만들어진다.

태우는 여부에 따른 바둑이의 수, 바둑이들의 무게의 합, 해당 배열을 매개변수로 사용한다.

 

import java.util.*;

public class Main {
    static int answer = Integer.MIN_VALUE, c, n;
    public void DFS(int L, int sum, int[] arr) {
        //트럭 용량보다 바둑이들을 더 많이 태울 순 없다. 
        if(sum > c) return;
        //태울 수 있는 용량 중 최대 무게를 구한다.
        if(L == n) {
            answer = Math.max(answer, sum);
        }
        else {
            //바둑이를 태운다.
            DFS(L+1, sum+arr[L] ,arr);
            //바둑이를 태우지 않는다.
            DFS(L+1, sum, arr);
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        c = kb.nextInt();
        n = kb.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        T.DFS(0, 0, arr);
        System.out.println(answer);
    }

}