[JAVA11/알고리즘] 8-2 바둑이 승차

 💬 문제

 

철수는 그의 바둑이들을 데리고 시장에 가려고 한다.

그런데 그의 트럭은 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를 이용한다고 봐도 무방하다.

모든 경우에서 c를 넘지 않는 최대치를 구하는 문제이다.

트리를 만들어서 모든 경우에서 c를 넘지 않는 것 중 최대치를 구한다고 생각하면 된다.

 

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);
        }

DFS 함수라고 하면 예전에는 엄청 어렵게만 느꼈는데, 그다지 어렵지않고 재귀를 이용해 간편하다고 생각든다.

 

먼저 타입인자로는, L,sum, int[] arr 를 받는다. L은 트리에서 level을 의미한다.

level이 n과 같아지면 탐색을 종료한다.

트리의 자식노드는 바둑이를 태운다, 안태운다 각각 두개로 나뉘어진다. 태우면 sum자리에 sum+arr[L]을 넣어서

다시 DFS를 재귀 호출하면 되는것이고 그렇지 않다면, sum을 그대로 넣어 재귀호출한다.

 

그 도중에 sum이 최대 한계값인 c보다 커지게되면 종료해주면 된다.

L이 n과 같아지면 트리의 가장 밑 레벨까지 왓다는 것이고 그 중에서 max 값을 골라내면된다.

👨🏻‍💻  CODE
 

import java.util.*;

public class Main {
    static int answer = Integer.MIN_VALUE,c,n;
    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) {
        Scanner in = new Scanner(System.in);
        c = in.nextInt();
        n = in.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = in.nextInt();
        }
        DFS(0,0,arr);
        System.out.println(answer);
    }
}

 

💪🏻 결과

 

한줄끄적: DFS 마스터를 향하여