바둑이 승차(DFS)

설명

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

 

문제 해결

 

철수가 가지고 있는 바둑이들 중에서 무게 C 를 초과하지 않으면서 가장 무거운 무게로 바둑이들을 트럭에 실을 수 있는 무게를 구하는 문제이다. 이는 DFS를 이용해 해결할 수 있다.

 

 

public class P02_바둑이승차_DFS {
    static int C, N;
    static int[] weights;
    static int max = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        C = in.nextInt();
        N = in.nextInt();
        weights = new int[N];

        for(int i = 0; i < N; i++) {
            weights[i] = in.nextInt();
        }

 

먼저 최대 허용 무게인 C, 바둑이의 총 마리 수 N, 바둑이의 무게를 저장할 배열인 weights, 최대 무게를 저장할 max를 전역변수로 선언해준다.

 

//태울지 말지
public static void DFS(int L, int sum) {
    if(sum > C) return; //C넘으면 return

    if(L == N) { //모든 바둑이 고려했을 때
        if(sum > max) //max 갱신
            max = sum;
    } else {
        DFS(L+1, sum + weights[L]); //바둑이 태울 때
        DFS(L+1, sum); //바둑이 태우지 않을 때
    }
}

 

DFS 함수를 작성해보자.

바둑이를 태울지 말지를 결정하며 이 조합수를 구해가면 된다.

먼저 탐색해갈 레벨(깊이) L과 바둑이를 태우며 무게를 저장할 sum을 입력받고,

• sum이 최대 허용 중량인 C를 넘으면 return 
• L (깊이) == N 즉 모든 바둑이를 고려했을 때, sum이 현재 최대 무게인 max보다 클 경우 max를 갱신시켜준다.
• 아직 모든 바둑이를 고려하지 않았다면
  • 바둑이를 태웠을 때 DFS(L+1, sum + weights[L])
    • L+1은 다음 바둑이의 인덱스로 이동을 의미, sum + weights[L]은 현재까지의 총 무게에 현재 바둑이의 무게를 추가한 것.
  • 태우지 않았을 때 DFS(L+1, sum) 
    • L+1은 똑같이 다음 바둑이로 이동하지만, sum은 변경되지 않음

 

이 DFS 함수를 main에서 DFS(0,0)으로 호출 (레벨0, sum0) 하고 max를 호출해주면 된다.

 

최종 코드

 

import java.util.Scanner;

public class P02_바둑이승차_DFS {
    static int C, N;
    static int[] weights;
    static int max = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        C = in.nextInt();
        N = in.nextInt();
        weights = new int[N];

        for(int i = 0; i < N; i++) {
            weights[i] = in.nextInt();
        }

        DFS(0,0); //레벨 0, sum 0
        System.out.println(max);
    }

    //태울지 말지
    public static void DFS(int L, int sum) {
        if(sum > C) return; //C넘으면 return

        if(L == N) { //모든 바둑이 고려했을 때
            if(sum > max) //max 갱신
                max = sum;
        } else {
            DFS(L+1, sum + weights[L]); //바둑이 태울 때
            DFS(L+1, sum); //바둑이 태우지 않을 때
        }
    }
}