[JAVA][백준 17845][배낭문제] 수강 과목 - 컴도리돌이

반응형

 

17845번: 수강 과목

---

 

17845번

DP문제 중에 knapsack 문제로 해결해야 합니다.

bag[M][N]을 1부터 M+1번째 과목들을 대상으로

최대 N시간을 써서 얻을 수 있는 

가장 큰 중요도를 구해야 합니다.

 

현재 i번째 시간으로 들을 수 있을 경우

이전 과목을 들은 경우와 현재 i번째 시간 전 + 현재 i번째 우선도를 비교해서 

최대 값으로 bag [i][j]를 갱신해줘야 합니다.

 

현재 i번째 시간으로 듣지 못할 경우는

이전 과목의 우선도를 할당해줍니다.

---

	package 배낭문제;
	import java.io.BufferedReader;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	public class boj17845 {
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int n = Integer.parseInt(st.nextToken()), k = Integer.parseInt(st.nextToken());
	int [] priority = new int[k+1];
	int [] time = new int[k+1];
	int [][] bag = new int[k+1][n+1];
	for(int i=1; i <=k ; i++){
	st = new StringTokenizer(br.readLine());
	priority[i] = Integer.parseInt(st.nextToken());
	time[i] = Integer.parseInt(st.nextToken());
	}
	// 배낭 문제
	for(int i=1; i<=k ; i++){
	for(int j=1; j <= n ; j++){
	if(time[i] <= j) {
	bag[i][j] = Math.max(bag[i-1][j],bag[i-1][j-time[i]] + priority[i]);
	}else{
	bag[i][j] = bag[i-1][j];
	}
	}
	}
	System.out.println(bag[k][n]);
	}
	}

view raw boj17845.java hosted with ❤ by GitHub