[BOJ 14728] 벼락치기

- 문제 요약

 

첫째 줄에는 이번 시험의 단원 개수 N(1<=N<=100)과 시험까지 공부할 수 있는 총 시간 T(1<=T<=10000)가 공백을 사이에 두고 주어진다. 둘째 줄부터 N줄에 걸쳐서 각 단원 별 예상 공부 시간 K(1<=K<=1000)와 그 단원 문제의 배점 S(1<=S<=1000)가 공백을 사이에 두고 주어진다. 남은 시간 동안 공부하여 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.

(단, 여러 단원을 융합한 문제는 출제하지 않는다. 한 단원에 한 문제를 출제하며, 어떤 단원의 문제를 맞추기 위해서는 그 단원의 예상 공부 시간만큼, 혹은 그보다 더 많이 공부해야만 맞출 수 있다.)

 

 

- 알고리즘 정리

 

냅색 문제입니다.

 

dp[x] = max(dp[x], dp[x-(예상 공부 시간)] + (문제 배점의 최대값))

위 점화식을 사용하여 해결할 수 있습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 10001
int n,t,dp[MAX],arr[101][2];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>arr[i][0]>>arr[i][1];
	}
	for(int i=1;i<=n;i++){
		for(int j=t;j>=arr[i][0];j--){
			dp[j]=max(dp[j],dp[j-arr[i][0]]+arr[i][1]);
		}
	}
	cout<<dp[t]<<endl;
}

코드 제출 결과