[백준] G5 17845번 수강 과목 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

17845번: 수강 과목

[문제] 

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

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

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

[입력]

첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다.

이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 공백을 사이에 두고 주어진다. 

[출력]

얻을 수 있는 최대 중요도를 출력한다.

 

 

---

[풀이]

1. dp문제 중 유명한 knapsack 문제처럼 풀면 된다.
2. 해당 시간이 맞다면 이전 dp값(이전까지의 중요도)과 현재의 시간이 빠진 이전 dp값에 현재 중요도를 더한 것의 최고값으로 입력해준다. (최고로 많이, 중요한 것을 해야 하니까)

3. 모든 주어진 것을 다 돌면 dp배열이 다 채워지고 마지막을 출력하면 결과이다.

[접근]

1. 문제를 보고 dp로 풀어야겠다고 생각이 떠올랐다.(배낭 문제)

2. 배낭 문제를 적용시켜서 문제를 풀었다.

[코드]

package BOJ_gold;

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

public class Main_G5_17845 {
	static int n;
	static int k;
	static int l[];
	static int t[];
	static int dp[][];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		l = new int[k + 1];
		t = new int[k + 1];
		dp = new int[k + 1][n + 1];
		
		for (int i = 1; i <= k; i++) {
			st = new StringTokenizer(br.readLine());
			l[i] = Integer.parseInt(st.nextToken());
			t[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = 1; i <= k; i++) {
			for (int j = 1; j <= n; j++) {
				if (j - t[i] >= 0) // 시간에 맞춰서 해결할수 있다면
					dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - t[i]] + l[i]);
				// 이전 dp값과 지금 시간을 뺀 이전 dp의 값에 현재 중요도를 더한 것을 비교
				// 최고값을 입력
				else { // 안된다면
					dp[i][j] = dp[i - 1][j]; // 이전값 입력
				}
			}
		}
		System.out.println(dp[k][n]);
	}
}