최대점수구하기DFS

코드

package algorithm08;

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
class 최대점수구하기DFS{
    static int answer=Integer.MIN_VALUE
            , n =5 /*문제 수*/
            , m =50/*제한 시간*/
            , sumN  /*문제 합*/
            , sumM; /*제한 시간 합*/
    
    static int[] nArr,mArr;
    
    //L은 레벨로 깊이라고 이해하면 된다.
    static void DFS3(int L) {
        //제한 시간을 넘기면 더 이상 볼 필요없다.
        if(sumM>m) return;
        
        //모든 노드 순회 완료
        if(L==n) {
            answer = Math.max(answer,sumN);
        //아직 순회할 것이 남았다.
        } else {
            //더 했을 때
            sumN+=nArr[L];
            sumM+=mArr[L];

            DFS3(L+1);
            //안 더했을 때
            sumN-=nArr[L];
            sumM-=mArr[L];
            DFS3(L+1);
        }
    }
    
    public static void main(String[] args){
        nArr=getIntArray(1, 15, n);
        mArr=getIntArray(10, 20, n);
        System.out.println(Arrays.toString(nArr));
        System.out.println(Arrays.toString(mArr));
        DFS3(0);
        System.out.println("제한 시간 내 최대 문제 "+ answer);
    }
    
    static int[] getIntArray(int start, int end, int limit) {
        return ThreadLocalRandom.current()
                .ints(start,end+1)
                .distinct()
                .limit(limit)
                .toArray();
    }
}

---

결과

[6, 1, 12, 8, 7]
[15, 12, 14, 17, 18]
제한 시간 내 최대 문제 27

---

주어진 문제 묶음에서 제한 시간내에 가장 많이 풀 수 있는 문제 수를 구한다.

고려해야할 값이 두 개라 헛갈릴 수 있지만, 사실상 한 값처럼 처리하면 된다.(같이 더 하고 같이 빼고)

그리고 조건만 좀 더 신경쓰면 그만이다.