[Ch.08 - DFS] 04. 바둑이 승차

2. 바둑이 승차(DFS)

 

설명

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 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

---

문제 풀이 순서

1. DFS -> O,X로 나눈다
2. 가장 무거운 무게를 찾기위한 if문 설정
   1. sum>n보다 크면 false
   2. L==m이면 Max값 리턴
   3. 그외엔 깊이탐색
      • DFS(L+1, sum+arr[L], arr);
      • DFS(L+1, sum, arr);

---

 

import java.util.Scanner;
//바둑이 승차 DFS
//C킬로그램미만으로 태울 수 있는 트럭
//바둑이들을 최대한 태우기 위해
//N마리의 바둑이
//각 바둑이의 무게 W
//태울 수 있는 가장 무거운 무게
class Main {
	static int n,m,answer;
	
	public void DFS(int L, int sum, int[] arr) {
		
		if(sum>n) {
			return;
		}
		if(L==m) {
			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 kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		int[] arr = new int[m];
		for(int i=0;i<m;i++) {
			arr[i]=kb.nextInt();
		}
		T.DFS(0,0,arr);
		System.out.println(answer);
	} 

}

 

+) arr를 전역변수로

import java.util.*;
  
public class Main {
  static int[] arr;
  static int c, n ,answer;
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    c = in.nextInt();
    n = in.nextInt();
    arr= new int[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
    }
    DFS(0,0);
    System.out.println(answer);
  }
  static void DFS(int L, int sum){
    if(c>=sum)
      answer=Math.max(answer, sum);
    if(L==n){
      return;
    }
    else{
      DFS(L+1, sum);
      DFS(L+1, sum+arr[L]);
    }
  }
}

 

import java.util.*;
  
public class Main {
  static int m,n, answer;
  static int[] arr;
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    m = in.nextInt();
    n = in.nextInt();
    arr= new int[n+1];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
    }
    DFS(0, 0);
    System.out.println(answer);
  }
  static void DFS(int L, int sum){
    if(L>n) return;
    if(sum>m) return;
    else{
      if(sum<=m)
      answer=Math.max(answer, sum);
      
      DFS(L+1, sum);
      DFS(L+1, sum+arr[L]);
    }
  }
}