[JAVA] 알고리즘 : DFS- 바둑이 승차

 

import java.util.Scanner;

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(); // n마리
        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);
    }
}