[PS] 인프런 강의 - 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

 

풀이

부분집합 문제랑 거의 비슷하다. 다만 이 문제에서는 재귀 탈출용 변수 flag가 필요없고,

최대값을 구해야 하기 때문에 answer 변수를 처음에 Integer.MIN_VALUE 값으로 초기화한다.

그리고 트리의 마지막 정점에 도달했을 때 무게 합계와 answer 를 비교해, 큰 값을 answer에 저장해야한다.

 

코드

import java.util.Scanner;

public class Main {
	
	static int answer = Integer.MIN_VALUE; //최대값을 구해야하니까
	static int[] w;
	static int c, n;
	
	public static void DFS(int i, int sum) {
		if(sum > c) return; //c보다 크면 돌아가기
		
		//마지막 정점
		if(i == n) {
			// 중에서 최대값
			answer = Math.max(answer, sum);
			return;
		}
		else {
			DFS(i+1, sum + w[i]);//i를 사용 -> 합계 더한다
			DFS(i+1, sum); //i를 사용X -> 합계 더하지 X
		}
	}

	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        c = in.nextInt(); //1~100,000,000
        n = in.nextInt();//1~30
        w = new int[n]; //바둑이 무게
        
        for(int i=0; i<n; i++) {
        	w[i] = in.nextInt();
        }
        
        //c를 넘지 않으면서 가장 무거운 w의 합(태우니까 중복X)
        DFS(0, 0);
        System.out.print(answer);
        
    }
}