자바 알고리즘 문제 풀이 입문. ch08. DFS, BFS 활용 : 바둑이 승차 DFS

 

https://hyejin.tistory.com/1266

자바 알고리즘 문제 풀이 입문. ch08. DFS, BFS 활용 : 합이 같은 부분 집합 (DFS, 아마존 인터뷰)

-> 이전 문제 풀이 

 

 

 

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

 

 

문제 풀이 1

public class BadukiRiding
{
   static int c, n, answer = 0;
   static int[] arr;
   
   // 부분 집합 코드와 거의 유사하게 풀면 된다.
   public void DFS(int L, int sum )
   {
      if (sum > c) {
         return;
      }
      if (L == n) {
         if (answer < sum) answer = sum;
      }else {
         DFS(L + 1, sum + arr[L]);
         DFS(L + 1, sum);
      }
   }
   
   public static void main(String[] args)
   {
      BadukiRiding badukiRiding = new BadukiRiding();
      Scanner scanner = new Scanner(System.in);
       c = scanner.nextInt(); // 최대 무게
       n = scanner.nextInt();
      arr = new int[n];
      for (int i = 0; i< n; i++)
      {
         arr[i] = scanner.nextInt();
      }
      
      badukiRiding.DFS(0, 0);
      System.out.println(answer);
      
   }
}

👩‍💻 : 이 문제는 이전 문제에서 풀었던 합이 같은 부분 집합 구하는 것과 동일하게 문제를 풀면 된다. (풀이 방식이 거~~의 비슷함) 

 

static int c, n, answer = 0;
static int[] arr;

-> 먼저 static 변수로 c, n, answer를 모두 선언해주는데 c는 최대 무게 n은 바둑이 마리 수, answer에 바둑이들을 태울 수 있는 최대 무게를 담을 변수이다. (arr은 각 바둑이들 무게) 

 

public void DFS(int L, int sum )
{
   if (sum > c) {
      return;
   }
   if (L == n) {
      if (answer < sum) answer = sum;
   }else {
      DFS(L + 1, sum + arr[L]);
      DFS(L + 1, sum);
   }
}

-> DFS 메서드에는 L (레벨)과 sum을 매개변수로 받을 것이다. 

만약 sum이 c를 초과하면 더 이상 바둑이를 태울 수 없기 때문에 그대로 리턴해준다. 

 

아니면 L이 바둑이 마리수만큼 더했다면 이제 이 sum이 answer 보다 크다면 answer에 sum 값을 담아준다. (c보다 큰 경우는 위에서 걸러줬기 때문에 그대로 담아도 된다.) 

 

이 경우도 아니라면 DFS를 호출할 때 sum에 해당 바둑이를 태운 합과, 태우지 않은 합을 각각 재귀 함수를 통해 호출해주면 된다. 

 

 

 

문제 풀이 2

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

public void DFS(int L, int sum, int[] arr)
{
   if (sum > c) return;
   if (L == n) {
      answer = Math.max(sum, answer);
   }else {
      DFS(L+1, sum + arr[L], arr);
      DFS(L+1, sum, arr);
   }
}

👾 : 강사님이 풀이한 방식도 거의 비슷하긴 하다. 다른 부분이라면 answer에 값을 구할 때 Math.max 메서드를 통해 sum과 answer 중에 큰 값을 answer에 담아주는 부분이다.