[BAE/<JOON> 문제풀이] 2109. 순회강연

https://www.acmicpc.net/problem/2109

2109번: 순회강연

서론

문제 서술이 그리디 같이 생겨서 그리디인 줄 알았는데 입력 사이즈는 DP라서 DP로 풀었다.

특이하게도 제출하는데 메모리가 빡빡했다.
 + 제출하고 다른 사람 코드보는데 pq 였네.. 근데 pq면 그리디 맞구나.

---

풀이

직관적으로 생각했을 때 걸린 제한시간이 적은 곳 부터 순회하는게 맞다.

정렬 후 배열을 순회하며 강연한 수에 따라 버려지는 강연을 구해 최적값을 연산한다. 

• DP[i][j] = i 번째 강연까지만 했고 j 개의 강연을 돌았을 때 벌 수 있는 가장 큰 돈
• DP[i][j] = max(DP[i - 1][min(j, 현재 강연 제한시간) - 1] + 현재 강연에서 벌 수 있는 돈, DP[i - 1][j])
  i번째 강연을 할 경우 현재 강연의 제한시간 - 1 개의 강의밖에 하지 못한다. 

추가로 제출 시 1억개 배열을 잡을 수 없으니 실제 연산이 진행되는 i번째, i - 1번째 구역만 슬라이딩 윈도우로 처리해서 AC를 맞았다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <cstdlib>
using namespace std;
struct node {
	int p, d; 
};
bool cmp(node a, node b) {
	return a.d < b.d;
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; vector<node> arr(n + 1); vector<int> dp1(n + 1), dp2(n + 1);	
	for (int i = 1; i <= n; i++) {
		cin >> arr[i].p >> arr[i].d;	
	}
	sort(arr.begin() + 1, arr.end(), cmp);
	for (int i = 1; i <= n; i++) { // 사용한 번호 
		for (int j = 1; j <= i; j++) { // 사용한 개수
			int nd = arr[i].d < j ? arr[i].d : j;
			int s1 = dp2[nd - 1] + arr[i].p;
			int s2 = dp2[j];
			dp1[j] = s1 > s2 ? s1 : s2;
		}
		dp2 = dp1;
	}
	cout << *max_element(dp1.begin(), dp1.end());
	return 0;
}