DFS 문제풀이 : 바둑이 승차, 잔돈 계산하기

오늘은 DFS 관련 문제를 풀고 공부해봤습니다. 

코드에 대한 설명은 주석에 달아두었습니다.

1. 바둑이 승차

※ 설명

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

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

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

※ 입력

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

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

※ 출력

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

 

package DFS;

import java.util.Scanner;
import java.util.concurrent.Callable;

public class DFS_shopping {

    static int n = 0; // 바둑이의 수
    static int total = 0; // 트럭에 태울 수 있는 최대 무게
    static int result = Integer.MIN_VALUE; // int 형의 최소값


    // 구매한 물품의 합계가 내가 현재 갖고잇는 돈보다 많으면 안된다는 것을 명심!!
    // 트럭에 탄 바둑이의 무게의 합계는 트럭의 최대 무게 보다 많으면 안된다.
    // 즉, total > sum
    public static void shopping(int num, int sum, int[] arr){
        if(sum>total) return; // sum 은 total 보다 크면 안된다.

        // 전체 바둑이를 한번씩 넣으면서 확인했을 때 모든 바둑이를 확인하면 끝
        if(num == n){
            // result 에 저장되었던 값과 트럭에 탄 바둑이의 최대값 중 비교
           result = Math.max(result, sum);
        }else{
            System.out.println("sum : "+sum);
            System.out.println("result : "+result);
            System.out.println("########################");

            // num 번째 바둑이를 트럭에 태우는 경우 sum+arr[num]
            shopping(num+1, sum+arr[num], arr);
            // num 번째 바둑이를 트럭에 태우지 안흔ㄴ 경우 sum
            shopping(num+1, sum, arr);
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        total = scan.nextInt(); // 트럭의 최대 무게
        n = scan.nextInt(); // 전체 바둑이의 수

        int[] arr = new int[n];

        for(int i = 0; i < n; i++){
            arr[i] = scan.nextInt();
        }

        // 처음에 0 번째 바둑이부터 시작, 첫 합계는 0, 바둑이들의 무게를 담은 배열이 넘어감감        shopping(0,0,arr);
        System.out.println("최대 결과 : "+result);
    }
}

 

2. 최대 점수 계산하기

※ 설명

이번 코딩테스트 대회에서 좋은 성적을 내기 위하여 나는 선생님이 주신 N개의 문제를 풀려고 한다

각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 된다

제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 한다

(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

 

※ 입력

첫 번째 줄에 문제의 개수N(1<=N<=20)과 제한 시간 M(10<=M<=300)이 주어집니다.

두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

 

※ 출력

첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.

package DFS;

import java.util.Scanner;

public class DFS_travel {
    static int n =0; // 문제 갯수
    static int m =0; // 문제 시간
    static int result = Integer.MIN_VALUE; // Integer 형 최솟값

    // 배열 인덱스, 점수 합계, 문제를 풀고 난 후 시간합계, 점수배열, 시간배열
    public static void travel(int num, int sum, int timeLimit, int[] score, int[] time){
        System.out.println("num : "+num);
        System.out.println("sum : "+sum);
        System.out.println("result : "+result);

        if(timeLimit > m) return; // 만약 timeLimit 가 제한시간  m보다 크다면 더 계산할 필요없음 return

        if(num == n){
            result = Math.max(sum,result); // 최대값 찾기
        }else{
            travel(num+1, sum+score[num], timeLimit+time[num], score, time);

            // num 번째 문제를 풀지 않는 경우 : sum 합계와 문제 푸는데 걸리는 시간 timeLimit 그대로
            travel(num+1, sum, timeLimit, score, time);

        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();

        int[] score = new int[n]; // 문제별 점수
        int[] time = new int[n]; // 문제별 시간

        for(int i=0; i<n; i++){
            score[i] = scan.nextInt();
            time[i] = scan.nextInt();
        }

        travel(0, 0,0,score,time);
        System.out.println("result : "+result);

    }
}