최대점수 구하기(DFS)

 

이것도 부분집합 개념의 문제라고 볼 수 있다. - 이걸 생각해낼 줄 알아야함

여기선 해당 인덱스의 문제를 푼다/풀지 않는다 라고 재귀호출

단, 제한 시간을 넘어가면서 풀 순 없다.

L번째에 있는 문제를 푼다/풀지 않는다 인것!

L == n이 되면 모든 문제를 푼 것 ~ 모든 문제를 풀지 않는 것에 대한 조합(?)들이 만들어진다.

푸는 여부에 따른 문제 수, 점수의 합, 시간의 합을 인자로 보낸다.

 

import java.util.*;

public class Main {
    static int answer = Integer.MIN_VALUE, n, m;
    public void DFS(int L, int sum, int time, int[] ps, int[] pt) {
        //풀기로한 문제들의 시간이 제한 시간을 초과하면 안된다.
        if(time > m) return;
        //제한 시간안에 문제들을 풀 수 있으면 점수들 중 최대를 넣는다.
        if(L == n) {
            answer = Math.max(answer, sum);
        }
        else {
            //문제를 푼다.
            DFS(L+1, sum+ps[L], time+pt[L], ps, pt);
            //문제를 풀지 않는다.
            DFS(L+1, sum, time, ps, pt);
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = kb.nextInt();
            b[i] = kb.nextInt();
        }
        T.DFS(0, 0, 0, a, b);
        System.out.println(answer);
    }

}