알고리즘) 최대점수 구하기(냅색 알고리즘)

문제 ✨

 문제의 개수 N(1<= N <= 50)과 제한 시간 M(10 <= M <= 300)이 주어지고, N개 문제의 점수와 시간이 주어진다고 할 때, 제한 시간안에 얻을 수 있는 최대 점수를 출력하라.

풀이 ✨

 최댓값을 구하는 문제기 때문에 result의 모든 요소(의 값)을 0으로 초기화한다. 얻는 점수는 최소값이 0이기 때문에 Integer.MIN_VALUE이 아닌 0으로 초기화한다.

 처음 이 문제에 대해 접근할 때에는 동전 교환 문제와 같이 접근하였다. 하지만 이 문제의 핵심은 한 문제는 한 번만 풀 수 있다는 점이다. 이를 위해서는 각 문제의 시간을 인덱스로 하는 요소부터 시작해서 마지막 요소까지 반복하는 과정을 반대로 바꾸는 것이다. 즉, 마지막 요소부터 해당 문제의 시간을 인덱스로 하는 요소까지 반복하게 되면 이들이 참조하는 요소의 값(result[j - list[i].time])들이 아직 0임을 이용해 문제를 최대 1번만 푸는 경우로 계산되게 된다.

작성 코드 ✍️

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

// 최대점수 구하기(냅색 알고리즘)
public class Main {
    static int n;
    static int m;
    static int[] result;
    static Problem[] list;

    static class Problem implements Comparable<Problem> {
        int score;
        int time;

        public Problem(int score, int time) {
            this.score = score;
            this.time = time;
        }

        @Override
        public int compareTo(Problem p) {
            return this.time - p.time;
        }
    }

    public void solution() {
        // 각 문제는 한번밖에 풀 수 없는 점에 유의할 것 💫
        result[0] = 0;
        for (int i = 0; i < list.length; i++) {
            for (int j = m; j >= list[i].time; j--) {
                result[j] = Math.max(result[j], result[j - list[i].time] + list[i].score);
            }
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 문제 수
        m = sc.nextInt(); // 제한 시간
        result = new int[m + 1];
        list = new Problem[n];
        for (int i = 0; i < n; i++) {
            int s = sc.nextInt();
            int t = sc.nextInt();
            list[i] = new Problem(s, t);
        }
        Arrays.sort(list);
        Arrays.fill(result, 0);

        main.solution();
        System.out.println(result[m]);
    }
}