설명
철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 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 c;
static int n;
static int max = 0;
public static void DFS(int L, int sum, int[] a) {
if(sum > c) return;
if (L == n) {
if (sum > max) max = sum;
} else {
DFS(L + 1, sum + a[L], a);
DFS(L + 1, sum, a);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
c = sc.nextInt();
n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
DFS(0, 0, a);
System.out.println(max);
}
}
'코딩연습이 좋아서 > 이론이 좋아서' 카테고리의 다른 글
DFS, BFS 활용 - 중복순열 구하기(DFS) (0) | 2024.12.13 |
---|---|
DFS, BFS 활용 - 최대점수 구하기(DFS) (0) | 2024.12.13 |
DFS, BFS 활용 - 합이 같은 부분집합(DFS : 아마존 인터뷰) (0) | 2024.12.13 |
Recursive, Tree, Graph(DFS, BFS 기초) - 그래프 최단거리(BFS) (0) | 2024.12.13 |
Recursive, Tree, Graph(DFS, BFS 기초) - 경로탐색(인접리스트, ArrayList) (0) | 2024.12.13 |