3. 최대 점수 구하기(DFS)

1. 문제

설명

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.

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

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

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

입력

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

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

출력

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

 

 

2 - 1. 나의 풀이

2번 바둑이 승차에서 변수가 하나 더 추가된 것 뿐이다.

 

return 조건은 시간의 누적합이 제한시간을 넘어가는 경우(time > limit)

문제의 점수와 시간은 2차원 배열 arr에 담고 [][0]에 점수를 [][1]에 시간을 담는다.

 

이후 바둑이 승차와 같이 DFS하면 끝!

 

2 - 2. 나의 코드

package DFS_BFS_levelup;
import java.util.*;

public class pratice_myself {
    public static int n; //문제 수
    public static int limit; //제한 시간
    public static int[][] arr; //문제와 푸는 시간을 담은 배열
    public static int answer=0;//답

    public static void DFS(int L, int sum, int time) {
        if(time > limit) return;
        if(L==n)answer = Math.max(answer, sum);
        else{
            DFS(L + 1, sum + arr[L][0], time + arr[L][1]);
            DFS(L + 1, sum, time );
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        limit = sc.nextInt();
        arr = new int[n][2]; //[][0]이 문제 [][1]이 시간
        for (int i = 0; i < n; i++) { //점수와 시간 배열에 저장.
            for (int j = 0; j < 2; j++) arr[i][j] = sc.nextInt();
        }

        DFS(0, 0, 0);
        
        System.out.println(answer);
    }
}

 

 

3 . 강의 풀이

나와 같다.

 

 

4. 얻어갈 점

DFS, BFS는 많이 풀어 보자.