2. 바둑이 승차(DFS)

1. 문제

트럭에 태울 수 있는 무게 한계치 W와 N마리의 바둑이와 바둑이의 무게들이 주어진다.

트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램

 

2 - 1. 나의 풀이

간단한 DFS 문제이다.

각 숫자들을 배열에 저장한 다음

arr[L]을 사용 or 미사용하면서 DFS 갈래를 뻗어나간다.

하지만 한계치 W를 넘어가면 중단하고 다음 으로 넘어간다.

 

2 - 2. 나의 코드

package DFS_BFS_levelup;
import java.util.*;


public class dfs02_myself {
    public static int w;
    public static int n;
    public static int[] arr;
    public static int answer;

    public static void DFS(int L, int sum) {
        if(sum > w) return; //한계치를 넘으면 return
        if(L==n)answer = Math.max(answer, sum);
        else{
            DFS(L + 1, sum + arr[L]); //arr[L] 사용
            DFS(L + 1, sum);		  //arr[L] 미사용
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        w = sc.nextInt();
        n = sc.nextInt();
        arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

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

 

3. 강의

나의 풀이와 같다.

 

 

4. 얻어갈 점

DFS는 많이 풀어보고 재귀함수의 흐름을 직접 따라가보는 것이 중요한 듯.