바둑이 승차(DFS)

13 May 2023 in Algorithm on Java, Coding, Test

문제

설명

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

해결방법

• 부분 집합을 만들어서 조건에 맞게 구한다음, 계속 바꿔치기 해서 답을 구하는 방식의 재귀를 띈다.

코드

import java.util.Scanner;

public class Main {

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

  public void DFS(int v, int sum, int[] arr) {
    // 무게 초과되면 끝.
    if (sum > c) {
      return;
    }
    if (v == n) {
      // 비교해서 큰 값을 정답으로 한다.
      answer = Math.max(answer, sum);
    } else {
      // 재귀 태우는 부분. 
      // 특정 순서 바둑이를 태우는 경우와 스킵하는 경우로 나뉜다.
      DFS(v + 1, sum + arr[v], arr);
      DFS(v + 1, sum, arr);
    }
  }

  public static void main(String[] args) {
    Main cls = new Main();
    Scanner kb = new Scanner(System.in);
    c = kb.nextInt();
    n = kb.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = kb.nextInt();
    }
    cls.DFS(0, 0, arr);
    System.out.println(answer);
  }
}