백준 17845 수강 과목

BOJ 17845

목표 : N개의 시간안에 T소요시간을 가지는 M개의 과목들을 수강해 얻을 수 있는 최대 중요도(I)를 구하기

조건 : 1 <= N <= 10000, 1 <= M <= 1000, 1 ≤ I ≤ 100000, 1 ≤ T ≤ 10000

해결방안

과목을 쪼개서 들을 수 없기에 0-1 배낭문제로 DP를 통해 해결할 수 있다. j의 소요시간을 가지며 i번째 과목을 선택했을 때 j시간에 얻을 수 있는 중요도의 최대값을 DP[i][j]으로 설정해 문제를 해결했다.

#include<stdio.h>
#include<algorithm>
using namespace std;
int N, M, dp[1001][10001]; // N번 무게에 M번째 과목을 들을 때 

int main(){
    scanf("%d%d",&N,&M);
    for (int i = 0; i < M; i++){
    	int val, time;
    	scanf("%d%d",&val,&time);
    	for (int j = 1; j <= N; j++){
    		if (time <= j){
            	// j-time시간을 소모하는 경우에야 현재 과목을 선택해도 소요시간이 N보다 작거나 같다.
    			dp[i+1][j] = max(dp[i][j],dp[i][j-time]+val);
			}
			else{
				dp[i+1][j] = dp[i][j];
			}
		}
	}
	printf("%d\n",dp[M][N]);
	
	return 0;
}

현재 들을 과목의 소요시간 : time, 현재 들을 과목의 중요도 : val
time보다 j가 작은 경우 : dp[i+1][j] = dp[i][j]
j시간을 소모해 i+1번째 과목까지 들었을 때의 최댓값을 j시간을 소모해 i번째 과목까지 들었을 때의 최댓값으로 초기화한다. (어차피 지금 과목을 듣기에는 시간이 부족하기 때문에)

time보다 j가 큰 경우 : dp[i+1][j] = max(dp[i][j],dp[i][j-time] + val)
j시간을 소모해 i+1번째 과목까지 들었을 때의 최댓값을 j시간을 소모해 i번째 과목까지 들었을 때의 최댓값과 j-time을 소모해 i번째 과목까지 들었을 때의 최댓값과 val의 합을 비교해 max값으로 초기화한다. (현재 과목을 선택하거나 이전에 수강했던대로 진행할 수 있다.)

O(NM)시간만에 해당 문제를 해결할 수 있다.