2515 전시장

Link

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

Detail

처음에는 일단 정렬을 하고 생각하기로 했다. 결국 앞에서 보는 기준이기 때문에 크기가 큰놈 뒤로 있으면 가려지기 때문 …

그 다음 최소 판매 기준인 sellable 길이에 대해서 생각했다. i번째를 팔아 먹을려면, sellable보가 보이는 길이가 부족할때 그 앞 작품을 “보여주지 않아야 …” !

여기서 아이디어가 떠올랐다. 클래식한 DP 계단 오르기 문제처럼, 각 작품에 대해서 (보여준다, 보여주지 않는다) 두가지 케이스로 나눠서 dp를 쌓아나가면 될 것 같았다.

dp 점화식은 다음과 같이 세웠다.

1. 전시 하지 않을 경우
   1. 그 앞 전시물까지 (전시를 했을 때, 전시를 하지 않았을 때) 두가지 경우중 큰 dp값
2. 전시 할 경우.
   1. 이 전시물을 팔 수 있도록 하기위해서 빼지 않아도 되는 전시물중 가장 높은값 i 에 대해 : i전시물을 (전시 했을 때, 전시 하지 않았을 때) 두 경우중 큰 dp 값 + 지금 전시물의 가격

이때 2-1경우를 구하는 과정에서, i 전시물을 선형적으로 구하려 할 경우 N^2 시간복잡도로 터지게 된다. (전시물의 수는 최대 30만개다.)

따라서 upper_bound (이진탐색) 함수를 통해서 NlogN으로 시간복잡도를 잡아줘야 문제를 통과할 수 있다.

Code

#include <bits/stdc++.h>
 
using namespace std;
 
int getMaxPrice(int sellable, vector<pair<int,int>>& items) {
	sort(items.begin(), items.end());
 
	// dp[0][i] = i번째 아이템을 전시하지 않았을 때 최대 가격
	// 전시하지 않을 수 있나? ==> 제일 큰 그림 뒤로 보내버리면 됨
	vector dp(2, vector(items.size(), 0));
 
	dp[1][0] = items[0].first >= sellable ? 0 : items[0].second;
	for(int i = 1; i < items.size(); i++) {
		dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]);
 
		// 가장 높은놈이 target_h보다 높으면 전시해도 의미가 없음. 이 길이보다 작은 최대값을 찾아야 함
		int target_h = items[i].first - sellable;
		auto highest = lower_bound(items.begin(), items.end(), make_pair(target_h+1, -1)) - 1;
		int highest_idx = highest - items.begin();
 
		dp[1][i] = max(max(dp[0][highest_idx], dp[1][highest_idx]) + items[i].second, dp[1][i - 1]);
	}
 
	return max(dp[0].back(), dp[1].back());
}
 
int main() {
	int N, sellable;
	cin >> N >> sellable;
 
	vector<pair<int, int>> h_and_p(N + 1);
 
	// upper_bound 하는 과정에서, 결과값에서 한번 앞으로 가기 때문에 길이가 0인 깡통 값이 하나 있어야 outofbound문제를 예방할 수 있다.
	h_and_p[0] = {0, 0};
	
	for(int i = 1; i <= N; i++) {
		cin >> h_and_p[i].first >> h_and_p[i].second;
	}
 
	cout << getMaxPrice(sellable, h_and_p) << endl;
}