[DFS] 바둑이 승차 .java

설명

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.

철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다

N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.

입력

첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다.

둘째 줄부터 N마리 바둑이의 무게가 주어진다.

출력

첫 번째 줄에 가장 무거운 무게를 출력한다.

예시 입력 1 

259 5
81
58
42
33
61

예시 출력 1

242

 

 

내 풀이

-> 부분집합 문제 => DFS

즉,  바둑이를 태운다 or 태우지 않는다 로 부분집합이 결정된다

 

import java.util.Scanner;


public class Main {

    static int c,n;
    static int answer =Integer.MIN_VALUE;


    public static void dfs(int L, int sum, int[] arr) {
        if(sum >= c) return;//c넘으면 재귀 종료
        if(L == n) {//모든 바둑이를 탐색했다면
            if(answer < sum) {//최댓값 갱신
                answer = sum;
            }
        } else {
            dfs(L+1,sum+arr[L],arr);//현재 바둑이 태움
            dfs(L+1,sum,arr);//안태움
        }


    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        c = sc.nextInt();
        n = sc.nextInt();

        int[] arr = new int[n];

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

        dfs(0,0,arr);
        System.out.print(answer);

    }

}

 

 

다른 풀이

최댓값 갱신 부분만 다르고 동일

import java.util.Scanner;


public class Main {

    static int c,n;
    static int answer =Integer.MIN_VALUE;

    public static 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 sc = new Scanner(System.in);
        c = sc.nextInt();
        n = sc.nextInt();

        int[] arr = new int[n];

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

        T.dfs(0,0,arr);
        System.out.print(answer);

    }

}

 

💡

DFS를 사용하는 부분집합 문제에 익숙해진 것 같다!!