문제

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

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

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

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

코드

public class MaximumScore {
    static int n,m=0;
    static int max = Integer.MIN_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int[] scores = new int[n];
        int[] times = new int[n];
        for(int i=0; i<n; i++){
            scores[i] = sc.nextInt();
            times[i] = sc.nextInt();
        }
        solution(scores, times);
        System.out.println(max);
    }
    public static void solution(int[] scores, int[] times){
        dfs(0,0,0, scores, times);
    }
    public static void dfs(int level, int time, int score, int[] scores, int[] times){
        if(time > m) return;
        if(level==n){
            max = Math.max(max, score);
        }else{
            dfs(level+1, time+times[level], score+scores[level], scores, times);
            dfs(level+1, time, score, scores, times);
        }
    }
}

설명

dfs를 통해 시간내 가장 많은 점수를 얻을 수 있는 풀이 방법을 찾는 알고리즘이다. 백트래킹을 통해 문제를 풀이하면 되는데 dfs 내의 로직 중 가장 상위의 time>m이면 return을 통해 시간 복잡도를 조금이라도 줄이고 우리의 문제의 제한점인 n에 도달했을 때 모든 문제를 풀이한 것이므로 max과 현재 score 점수를 비교하여 담아준다. 그리고 마지막으로 n에 도달하지 못한 상황에서는 dfs의 호출을 문제를 풀어냈을때와 풀지 않았을때로 나누어 적용시켜 문제를 풀이했다.

dfs 개념을 처음에는 머리에 넣기 힘들었는데 그냥 계속 푸니까 어느정도 머리에 들어오고 있는거 같긴하다... 문제를 읽고 어떻게 풀어야겠다라는 개념은 잡힌거 같은데 더 꼬아서 활용 문제가 나오면 풀수 있을까ㅜㅜㅜ

그래도 강의에 나오는 강사님의 코드와 거의 일치하게 풀어내서 기분은 좋았다.