<DP> BOJ 17845 수강 과목

김민석·2021년 3월 9일
0

알고리즘

목록 보기
17/27

문제

서윤이의 최대 공부시간 N이 주어지고 각 과목에 필요한 공부시간과 중요도가 주어진다. 최대 공부시간안에 가장 큰 중요도를 출력하는 문제입니다.

  • 최대 공부시간 1<= N <= 10000
  • 과목 수 1 <= K <= 1,000

접근

  1. 매우 전형적인 knapsack problem 입니다.
  2. d[N][M]d[N][M]을 0 - M번째 과목들을 대상으로 최대 N시간을 써서 얻을 수 있는 가장 큰 중요도로 정의합니다.
  3. M번째 과목을 들을지 안들을지를 이용해서 이런 점화식을 세웁니다.
  • 안듣는 경우
    d[N][M1]d[N][M-1]
  • 듣는 경우
    d[Nt[M]][M1]+v[M]d[N-t[M]][M-1]+v[M]

d[N][M]=Math.max(d[N][M1],d[Nt[M]][M1]+v[M])d[N][M] = Math.max(d[N][M-1], d[N-t[M]][M-1]+v[M])

  1. 초기값에 대하여 헷갈린다면 아래를 생각해보자.
    사실 제가 초기값을 정하는게 헷갈려서 적어봅니다..
    • n < 0
      n이 0보다 작으면 주어진 시간보다 더 많이 썼다는 것이므로 모든 값을 상쇄시킬 정도로 작은 값인 - 최대 과목 수 x 최대 중요도를 return해줍니다.
    • n == 0
      주어진 시간에 맞게 시간을 썼다는 것이므로 0을 return 해줍니다.
    • m < 0
      주어진 과목이 없으므로 어떻게 해도 0밖에 될 수 없습니다. 따라서 0을 return 합니다.

JAVA 코드

import java.io.*;
import java.util.*;

class baek__17845 {
    static int[][] d = new int[10001][1000];
    static int[] v;
    static int[] t;

    static int go(int n, int k) {
        if (n <= 0) {
            if (n == 0)
                return 0;
            return -100000000;
        }
        if (k < 0)
            return 0;

        if (d[n][k] != -1)
            return d[n][k];

        d[n][k] = Math.max(go(n, k - 1), go(n - t[k], k - 1) + v[k]);

        return d[n][k];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] temp = br.readLine().split(" ");

        int n = Integer.parseInt(temp[0]);
        int k = Integer.parseInt(temp[1]);

        v = new int[k];
        t = new int[k];
        for (int i = 0; i < k; i++) {
            temp = br.readLine().split(" ");
            v[i] = Integer.parseInt(temp[0]);
            t[i] = Integer.parseInt(temp[1]);
        }

        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < k; j++) {
                d[i][j] = -1;
            }
        }

        System.out.print(go(n, k - 1));
    }
}
profile
누구나 실수 할 수 있다고 생각합니다. 다만 저는 같은 실수를 반복하는 사람이 되고 싶지 않습니다. 같은 실수를 반복하지 않기 위해 기록하여 기억합니다.🙃

0개의 댓글