[BAE/<JOON> 문제풀이] 2515. 전시장

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

2515번: 전시장

서론

로직은 맞게 짰는데 이분 탐색 특유의 인덱싱 때문에 맞왜틀을 1시간 넘게 했다. 진짜 개싫다. 솔직히 아직도 틀린 코드가 왜 틀렸는지 모르겠다. 아무리 봐도 로직이 똑같다.

풀이

우선 입력 사이즈를 보면 n log n 이상의 알고리즘을 사용할 수 없다는걸 알 수 있다.

그림을 크기 순으로 정렬하면 다음과 같은 점화식을 세울 수 있다.

• DP[i] = max(DP[i - 1], DP[현재 그림이 팔릴 만큼 보이게하는 인덱스] + 현재 그림 가치) 

점화식은 간단하다. 그럼 저 현재 그림이 팔릴만큼 보이게하는 인덱스라는 걸 구해보자

lower_bound 함수를 이용해 구할 수 있다.

현재 그림이 팔릴 수 있으려면 그림의 높이 h - 가시영역제한 m 보다 앞에 있는 그림의 높이가 낮거나 같아야 한다.

즉 앞에 크기 순으로 정렬된 그림의 높이 중 h - m 보다 크거나 같은 그림이 나오는 처음 인덱스 idx를 구하고 그 인덱스 -1한 위치가 현재 그림이 팔릴 수 있게 되는 마지막 위치이다.

현재 그림을 팔았을 때와 현재 그림을 포기하고 이전의 가장 비싸게 팔리는 경우를 비교해 더 큰 결과를 저장하면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <list>
using namespace std;
using ll = long long;
struct pa {
	ll h, c;
};
bool cmp(const pa& a, const pa& b) {
	return a.h < b.h;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	ll n, m; cin >> n >> m; vector<pa> arr(n + 1); vector<int> dp(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> arr[i].h >> arr[i].c;
	}
	sort(arr.begin(), arr.end(), cmp); 	
	for (int i = 1; i <= n; i++) {
		ll p = arr[i].h - m;
		auto k = lower_bound(arr.begin(), arr.end(), p, [](const pa a, ll b) { return a.h <= b; });
		int idx = k - arr.begin();
		ll s1 = dp[idx - 1] + arr[i].c;
		ll s2 = dp[i - 1];
		dp[i] = s1 > s2 ? s1 : s2;
	}
	cout << dp[n] << "\n";
	for (int i = 1; i <= n; i++) {
		//cout << dp[i] << " ";
	}
	return 0;
}