[Algorithm] 최대점수 구하기(DFS)

설명

정보올림피아드대회에서 N개의 문제를 풀려고 합니다.

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

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

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

 

입력

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

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

 

출력

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

 

예시 입력 / 출력

5 20 10 5 25 12 15 8 6 3 7 4

41

 

---

 

풀이.

public class Main {

    static int n; // 문제의 갯수
    static int m; // 제한시간
    static int result = 0; // 결과 값
    static int[] scoreArr; // 점수 배열
    static int[] timeArr; // 시간 배열

    static void DFS(int level, int timeSum, int scoreSum){

        if(timeSum > m) return; // 현재 level까지의 timeSum이 제한시간 m보다 크면 return;
        if(level == n){ // 마지막 level도착 후 조건 확인
            if(result < scoreSum){ // 현재 level까지 의 scoreSum이 결과 값 보다 크면 대입
                result = scoreSum;
                return;
            }
        }else{
            // 문제를 푼다. (O)
            DFS(level+1,timeSum+timeArr[level], scoreSum+scoreArr[level]);
            // 문제를 풀지 않는다. (X)
            DFS(level+1, timeSum, scoreSum);
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // n개의 문제
        m = sc.nextInt(); // 제한시간 m
        scoreArr = new int[n];
        timeArr = new int[n];
        for (int i = 0; i < n; i++) {
            scoreArr[i] = sc.nextInt(); // 점수 배열
            timeArr[i] = sc.nextInt(); // 시간 배열
        }
        // level:0 , timeSum:0, scoreSum:0을 넘긴다.
        // ex) level1 - index0 / level2 - index1
        DFS(0,0, 0);
        System.out.println(result);

    }
}

 

---

 

정리 :

1. 이진트리 구조를 펜으로 그려가면서 구상 한다.

2. level을 1부터 시작 설정

3. 문제당 문제를 푼다(O), 문제를 풀지 않는다(X) 2개의 경우의 수 발생