백준 17845 - 수강 과목

Java

17845 번 - 수강 과목

문제

모든 과목의 중요도와, 일정 이상의 학점을 받기 위해 필요한 공부시간을 다 적었다.

공부 시간의 한계를 초과하지 않으면서 과목의 중요도 합이 최대가 되도록 몇 개만 선택하여 수강하기로 마음먹었다.

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

접근 방법

Knapsack Problem으로 해결한 문제이다.

코드

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

public class Main {
	static int n, k, result;
	static int[][] dp;
	static int[][] reward;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	k = stoi(stk.nextToken());
    	
    	reward = new int[k + 1][2];
    	dp = new int[k + 1][n + 1];
    	int I,T;
    	for(int i = 1; i <= k; i++) {
    		stk = new StringTokenizer(br.readLine());
    		I = stoi(stk.nextToken());
    		T = stoi(stk.nextToken());
    		reward[i][0] = I;		// 중요도
    		reward[i][1] = T;		// 공부 시간
    	}
    	
    	for(int i = 1; i <= k; i++) {
    		for(int j = 1; j <= n; j++) {
    			dp[i][j] = dp[i - 1][j];	// 현재 무게에서 이전까지 과목을 담은 최대 중요도를 넣는다.
    			if(reward[i][1] <= j) {		// 현재 과목을 넣을 수 있으면 이전까지 넣은 최대 중요도에서 추가한다
    				dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - reward[i][1]] + reward[i][0]);	// 비교
    			}
    		}
    	}
    	
    	System.out.println(dp[k][n]);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

Knapsack Problem을 복습하는 문제였다.

개선할 점

없습니다.