[알고리즘] 8-2 바둑이 승차 - DFS(깊이우선탐색) (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/08-02
• 문제 설명 : N마리의 바둑이와 각 바둑이의 무게 W, 트럭에 태울 수 있는 최대 무게 C가 주어졌을 때 트럭에 바둑이들을 태울 수 있는 가장 무거운 무게를 구하는 문제

풀이

• DFS(깊이우선탐색)으로 바둑이를 트럭에 태우는 모든 경우의 수를 구하며 바둑이들의 무게 합이 c보다 작지만 가장 큰 값을 구한다.

package inflearn.dfs_bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//바둑이 승차(DFS)
public class Main8_2 {

    static int c, n;
    static int max = 0;

    public static void dfs(int level, int sum, int[] arr) {
        if (sum > c)
            return;

        if (level == n)
            max = Math.max(max, sum);
         else {
            dfs(level + 1, sum + arr[level], arr);
            dfs(level + 1, sum, arr);
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        c = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        dfs(0, 0, arr);

        System.out.println(max);

        br.close();
    }
}