백준2515 전시장

작성일 | In

문제 링크

  • http://icpc.me/2515

문제 출처

  • 2012 전국 본선 중등2

사용 알고리즘

  • DP

시간복잡도

  • O(C + N)

풀이

dp[n]을 첫 번째부터 n번째까지의 그림만을 고려했을 때의 정답이라고 정의합시다.
i번째 그림을 무조건 전시한다고 할 때, 앞에 전시할 수 있는 가장 높은 그림의 번호를 dd[i]에 저장합시다. 반복문 1개를 이용하여 dd배열을 채울 수 있습니다.

이제 dp배열을 채워봅시다. 위에서 dp[i]는 첫 번째부터 i번째까지의 그림만을 고려했을 때의 정답이라고 정의했고, dd[i]는 i번째 그림을 무조건 전시할 때 그보다 앞에 전시할 수 있는 가장 높은 그림을 저장하고 있습니다.
그러면 i번째 사진을 무조건 전시할 때 가격의 합의 최대는 (dd[i]번째 그림을 전시했을 때의 최대 + i번째 그림의 가치) 즉, (dp[dd[i]] + picture[i].value)라고 할 수 있습니다.
dp[i]는 첫 번째부터 i번째까지의 그림만을 고려했을 때 i번째 그림을 전시할 때의 최대값 혹은 i번째 그림을 전시하지 않을 때의 최대값 중 하나가 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

int n, s;

typedef pair<int, int> p;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> s;
	vector<p> v(n+1);
	for(int i=1; i<=n; i++) cin >> v[i].first >> v[i].second;
	sort(v.begin()+1, v.end());
	vector<int> d(n+1), dd(n+1);

	for(int i=1; i<=n; i++){
		for(dd[i]=dd[i-1]+1; dd[i]<i; dd[i]++){
			if(v[i].first-v[dd[i]].first < s) break;
		}
		dd[i]--;
	}

	int ans = 0;

	for(int i=1; i<=n; i++){
		d[i] = d[dd[i]] + v[i].second;
		d[i] = max(d[i], d[i-1]);
	}

	cout << d[n];
}