[백준 2515] 전시장

전시장 2515

유형

• DP

풀이

메모이제이션이 필요한 dp문제였다. 일단 높이 오름 -> 가격 내림차순으로 정렬하고 시작하였다.

테이블은 1차원으로 dp[i]는 i번째까지 최대 가격합으로 설정하였다.

점화식은 dp[i](i번째까지 최대합)은 현재보다 높이가 S이상으로 낮은 물건의 인덱스들 중 가장 큰 값을 가져오는 방식으로 했다. 말로 설명하니 조금 이상한데 코드를 보면 알 수 있을 것이다. 이전 인덱스에 높이 조건을 만족하는 것이 없을 수 있기 때문에 비교 후 마지막에 현재 값과의 비교를 dp[i] = max(dp[i], v[i].second) 넣어주었다.

코드

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

int n, c;
pair<int, int> v[300001];
int dp[300001];

bool cmp(pair<int, int>&a, pair<int, int>& b){
	return a.first == b.first ? a.second > b.second : a.first < b.first;
}

int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> c;
	for (int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;

	sort(v, v + n, cmp);

	dp[0] = v[0].second;
	int prev = 0;

	for (int i = 1; i < n; i++) {
		for (int j = prev; v[j].first + c <= v[i].first; j++) {
			if (dp[i] < dp[j] + v[i].second) {
				prev = j;
				dp[i] = dp[j] + v[i].second;
			}
		}
		dp[i] = max(dp[i], v[i].second);
	}
	cout << *max_element(dp, dp + n);

	return 0;
}