[백준] 17845 수강 과목 - Knapsack(배낭문제, 냅색) + DP(Dynamic Programming) JAVA

https://www.acmicpc.net/problem/17845

17845번: 수강 과목

코드설명

 Knapsack(배낭문제, 냅색) + DP(Dynamic Programming) 을 활용하는 문제입니다.

 

냅색 알고리즘을 사용하면 해결할 수 있습니다.

주요 로직입니다.

• simulate 메서드는 현재 레벨과 남은 공부 시간을 인자로 받아 최대 중요도를 계산합니다.
• 재귀적으로 다음 레벨의 과목을 선택하거나 선택하지 않는 경우의 중요도를 계산하여 최대값을 구합니다.
• 중복 계산을 방지하기 위해 메모이제이션을 사용하며, 계산된 결과는 dp 배열에 저장됩니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
	public static int N, M, K;
	public static Subject[] subject;
	public static int[][] dp;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		subject = new Subject[K];
		dp = new int[K][10001];
		for(int i=0;i<K;i++) {
			st = new StringTokenizer(br.readLine());
			int inputImportance = Integer.parseInt(st.nextToken());
			int inputStudyTime = Integer.parseInt(st.nextToken());
			
			subject[i] = new Subject(inputImportance, inputStudyTime);
			Arrays.fill(dp[i], -1);
		}
		answer = simulate(0, N);
		System.out.println(answer);
	}
	
	public static int simulate(int level, int studyTime) {
		if(studyTime == 0) {
			return 0;
		}
		if(level >= K) {
			return 0;
		}
		if(dp[level][studyTime] != -1) return dp[level][studyTime];
		
		int resultA = 0, resultB = 0;
		if(studyTime - subject[level].studyTime >= 0) {
			resultA = subject[level].importance + simulate(level + 1, studyTime - subject[level].studyTime);
		}
		resultB = simulate(level + 1, studyTime);
		
		return dp[level][studyTime] = Math.max(resultA, resultB);
	}
}
 
class Subject{
	int importance;
	int studyTime;
	public Subject(int importance, int studyTime) {
		this.importance = importance;
		this.studyTime = studyTime;
	}
}