[백준 13904] 과제

이 문제를 처음 봤을때 dp로 풀어야겠다 생각함

이유는 아래와 같다

 

1. 높은 점수부터 쌓는다고 최댓값이 되는게 아니다

2. 그렇다고 마감 빠른 것부터 쌓는다고 최댓값이 되는게 아니다

 

즉 특정 명제를 참으로 두고 매 순간 선택했을시 답이 나오는게 아니기 때문이다.

그래서 모든 경우의 수를 해보는 dp가 맞다고 생각함

 

배낭문제처럼 접근함

 

1번째 과제 했을 경우 최댓값

1~2번째까지 했을 경우 최댓값

1~3번째까지 했을 경우 최댓값

 

근데 여기서 중요한게 마감일 순으로 정렬하고 해야함

그래야 2차원 dp가 맞게 나온다

 

 

dp[i][k] : i 과제까지 넣었을때 k일까지 할 수 있는 최댓값

dp[i-1][k] : i-1 번째 과제까지 넣었을때 k일까지 할 수 있는 최댓값

dp[i-1][k-1] : i-1 번째 과제까지 넣었을때 k-1일까지 할 수 있는 최댓값

 

---

#include <iostream>
#include <vector>
#include <algorithm>

#define SIZE 1001

using namespace std;

int dp[SIZE][SIZE];

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

	int N, d, w;
	vector<pair<int, int>> v;
	v.push_back(make_pair(0, 0));

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> d >> w;
		v.push_back(make_pair(d, w));
	}

	sort(v.begin(), v.end());

	// 기한 일 수 넘으면 더해주면 안됨
	// 즉 k<=N 으로 돌리는데 if문 처리해줄거냐
	// 아니면 정렬하고 해당 기한까지만 돌릴거냐
	// 똑같음

	for (int i = 1; i <= N; i++) {
		int day = v[i].first;
		int value = v[i].second;
		for (int k = 1; k <= day; k++) {
			dp[i][k] = max(dp[i][k-1], max(dp[i - 1][k], dp[i - 1][k - 1] + value));
		}
	}
	
	cout << dp[N][v.back().first];
	
	return 0;
}