Java : 바둑이 승차 (DFS)

• 풀이

• 최대 무게를 넘지 않는 선에서 최대 값을 dfs 돌면서 계속 갱신해준다.

코드

package inflearn;

import java.util.Arrays;
import java.util.Scanner;

public class I0802 {

  static int ans = 0, c;
  static int[] arr;

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    c = sc.nextInt();
    int n = sc.nextInt();
    arr = new int[n + 1];

    for (int i = 1; i <= n; i++) {
      arr[i] = sc.nextInt();
    }
    Arrays.sort(arr);
    int l = 0;
    dfs(l, arr[0]);
    System.out.println(ans);
  }

  static void dfs(int level, int data) {
    if (c >= data && data > ans) ans = data;
    if (level == arr.length - 1) return;
    dfs(level + 1, data + arr[level + 1]);
    dfs(level + 1, data);
  }
}