[인프런] 08_02 바둑이 승차(DFS)

📖  문제

---

• 첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다.
• 둘째 줄부터 N마리 바둑이의 무게가 주어진다.
  • 철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.
  • 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.
  • N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.

출력 예시

 

⚠️  주의사항

---

• 넘게 태우는게 불가능하므로 같은 경우까지는 가능
• 가장 무거운 값 출력

 

✍️  이해

---

/**
 * 1. 08_01과 흡사한 문제
 * 2. 주어진 입력들 입력 받기
 * 3. 무게의 합이 C 보다 크면 바로 return
 * 4. line = N인 경우 Math.max(이전까지 더해진값, 현재값)
 * 5. DFS(line+1, total+현재값, arr)
 * 6. DFS(line+1, total, arr)
 */

 

✏️  풀이

---

import java.util.Scanner;

public class Main {

    static int[] arr;
    static int C, N, answer = 0;

    public void DFS(int L, int total, int[] arr) {
        if(total > C) return;
        else{
            if(L == N) {
                answer = Math.max(answer, total);
            }else {
                DFS(L + 1, total + arr[L], arr);
                DFS(L + 1, total, arr);
            }
        }
    }
    public static void main(String[] args) {
        Main T = new Main();

        Scanner sc = new Scanner(System.in);
        C = sc.nextInt();
        N = sc.nextInt();
        arr = new int[N];

        int total = 0;

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
            total += arr[i];
        }

        T.DFS(0, 0, arr);
        System.out.println(answer);
    }
}

---