백준 17845 수강 과목

유니스트 컴퓨터공학과에 다니는 서윤이는 이번에 어떤 과목을 들을지 고민중이다. 학점을 잘 받을 수 있으면서도 중요한 과목을 듣고 싶은 서윤이는 모든 과목의 중요도와, 일정 이상의 학점을 받기 위해 필요한 공부시간을 다 적었다.

처음에는 모든 과목을 들으려고 했던 서윤이는 자신의 공부 시간에 한계가 있다는 것을 깨달았다. 그래서, 공부 시간의 한계를 초과하지 않으면서 과목의 중요도 합이 최대가 되도록 몇 개만 선택하여 수강하기로 마음먹었다.

중요도가 최대가 되도록 과목을 선택했을 때, 최대가 되는 중요도를 출력하는 프로그램을 작성하시오.

과목 수가 1000개이기 때문에 완탐으로 풀 수 없다고 판단했다.

조건은 공부 시간의 한계를 초과하면 안된다.

최대 공부시간은 10000이기 때문에 DP Table을 만들 수 있다고 판단했다(메모리 제한 확인)

과목들을 순회하면서 Time Table을 갱신했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int DP[] = new int[N + 1];

        int clist[] = new int[K + 1];
        int vlist[] = new int[K + 1];

        for(int i = 1; i <= K; i++) {
            st = new StringTokenizer(br.readLine());
            int imp = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            clist[i] = cost;
            vlist[i] = imp;
        }

        for(int i = 1; i <= K; i++) {
            int cost = clist[i];
            int imp = vlist[i];
            for(int j = N; j >= 1; j--) {
                if(cost <= j) {
                    DP[j] = Math.max(DP[j], DP[j - cost] + imp);
                }
            }

        }


        System.out.println(DP[N]);
    }

}