문제

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

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

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

코드

public class DogRide {
    static int n,m,sum,max;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        dfs(0,0, arr);
        System.out.println(max);
    }
    public static void dfs(int level, int sum, int[] arr){
        if(level == n){
            if(sum<m){
                max = Math.max(sum, max);
            }
        }else{
            dfs(level+1, sum+arr[level], arr);
            dfs(level+1, sum, arr);
        }
    }
}

설명

이것도 저번 시간에 풀어냈던 부분집합의 문제와 동일하다.
합이 같은 부분 집합(아마존 인터뷰)

위의 풀이는 내가 저번시간에 약속했듯이 직접 풀어보았다. 직접 풀수 있었던 이유는 이전 문제와 진짜 동일하기 때문이다ㅜㅜㅜ 그래도 풀어내서 기분 좋다 ㅜㅜ 여기서 강사님의 코드와 차이점은 dfs 내부에 첫줄에

if(sum>m) return;

이 들어가고 level==n일때 따로 검사를 하지 않는 것인데 저 코드를 나도 생각은 했었는데 return 해버리면 다음 강아지들을 비교하지 않는데 그럼 되나? 싶어서 넣지 않았다. 근데 그건 바보 같은 생각이였다... 왜냐하면 내가 작성한 코드는 무게가 초과해도 일단 강아지를 다 태우고 본다. 그 후에 무게가 초과했는지 확인하는 코드인데 이렇게 되면 이미 무게가 초과한 상태로 비교하므로 쓸데 없는 비교 코드가 실행된다. 그러므로 앞에 저 코드를 추가해서 시간 복잡도를 조금이라도 줄이자 ㅜㅜ

그래도 내가 직접 풀어냈다는 것에 감사하며 다음 문제도 풀어보자ㅜㅜㅜ