[알고리즘/java] DFS 활용 / 바둑이 승차

이 글은 인프런 [자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 ] 강의를 수강하며 작성한 글입니다.

- https://inf.run/Azjw

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

 

 

문제 :

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울 수가 없다.

철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.

N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하시오.

 

입력 :

첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어진다.

둘째 줄부터 N마리 바둑이의 무게가 주어진다.

 

출력 :

첫 번째 줄에 가장 무거운 무게를 출력한다.

 

예시 입력 :

259 5
81
58
42
33
61

예시 출력 1

242

 

---

 

 

문제를 읽어보면 저번 글의 부분집합 구하기와 같은 방식으로 문제를 풀 수 있다.

2021.12.27 - [알고리즘/자바 알고리즘 문제풀이: 코딩테스트 대비] - [알고리즘/java] DFS 활용 / 합이 같은 부분집합

[알고리즘/java] DFS 활용 / 합이 같은 부분집합

 

 

 

바둑이들을 입력 받아 하나의 집합 arr[] 로 만들고, 전체 집합에서 부분집합을 DFS로 구한다.

여기서 부분집합 내의 바둑이들의 몸무게합이 주어진 C값보다 크면 안되기 때문에, 몸무게 핪이 C보다 크면 종료시킨다.

 

 

그리고 하나의 부분집합이 만들어지면 (L==n), 가장 무거운 몸무게 합을 구하기 위해 answer값과 현재 몸무게합을 비교하여 큰 값을 answer에 저장한다.

 

 

 

 

< 바둑이 승차 전체 코드>

import java.util.*;

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