문제

---

풀이

그리디 (오답)

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

// N은 최대 100 
// 남은 시간 동안 얻을 수 있는 최대 점수 
// 그리디하게 점수가 높은 단원부터 공부하자. 

int N, totalTime;
vector<pii> v;

bool compare(pii a, pii b){
	if(a.first == b.first){ // 점수가 동일하면 
		return a.second < b.second; // 시간이 적은 것부터 
	}
	return a.first > b.first; // 점수가 높은 것부터 
}

void input(){
	cin >> N >> totalTime;

	for(int i = 0; i < N; i++){
		int time, score;
		cin >> time >> score;
		v.push_back({score, time});
	}

	// 점수를 기준으로 내림차순 정렬 
	sort(v.begin(), v.end(), compare);
}

void solution(){
	int studyTime = 0;
	int score = 0;
	
	for(int i = 0; i < N; i++){
		studyTime += v[i].second;
		if(studyTime <= totalTime){
			score += v[i].first;
		}else break;
	}

	cout << score;
}

int main()
{ 
	ios::sync_with_stdio(0);
	cin.tie(0);

	input();
	solution();
	
	return 0;
}

예외 케이스
4 10
10 10
3 9
3 9
3 9

점수가 높은 것부터 먼저 공부한다고 최대 점수를 얻을 수 있는 건 아니다.

위의 예시에서도 3시간 공부해서 9점 획득할 수 있는 단원을 3개 공부하면, 총 27점으로 최대 점수다.

그런데 그리디하게 점수가 높은 것부터 공부하면 10점밖에 획득하지 못한다.

---

DP

모든 경우의 수를 따지는 DP로 해결할 수 있을까?

• 부분 문제가 중복되는가?
• 부분 문제의 해를 모아서 최종적인 해를 구할 수 있는가?

점화식을 어떻게 세워야 할까? (평범한 배낭 문제와 매우 유사한 문제라는 걸 이쯤에서 알아차렸다.)

제한된 시간 동안 얻을 수 있는 최대 점수를 구해야 하므로

dp[i][j] : i번째 단원까지 공부하고, 시험까지 남은 시간이 j일 때 얻을 수 있는 최대 점수

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N_MAX = 101;
const int T_MAX = 10001;
int N, T;
int dp[N_MAX][T_MAX];
int times[N_MAX];
int scores[N_MAX];

void input(){
	cin >> N >> T;

	for(int i = 1; i <= N; i++){
		cin >> times[i] >> scores[i];
	}

	for(int i = 0; i <= T; i++){
		dp[0][i] = 0;
	}

	for(int i = 0; i <= N; i++){
		dp[i][0] = 0;
	}
}

void solution(){
	for(int i = 1; i <= N; i++){ // 1~i 단원까지 고려 
		for(int t = 1; t <= T; t++){ // 제한 시간 1~T
			int ti = times[i];
			int si = scores[i];

			// i번째 단원의 학습 시간이 제한 시간을 넘는 경우 
			if(ti > t) {
				// (i-1)번째 단원까지만 공부한다. 
				dp[i][t] = dp[i - 1][t];
			}else{
				// i번째 단원을 학습할지 말지 결정한다.
				dp[i][t] = max(dp[i - 1][t], dp[i - 1][t - ti] + si);
			}
		}
	}

	// N개의 단원을 모두 고려하고, 시험까지 남은 시간이 T일 때
	// 얻을 수 있는 최대 점수
	cout << dp[N][T];
}

int main()
{ 
	ios::sync_with_stdio(0);
	cin.tie(0);

	input();
	solution();
	
	return 0;
}