2515

옛날에는 못풀다가 컨디션 좋은날 불현듯이 아이디어가 생각나서 풀었다. 예전에 내가 풀었던 방식은 DP였긴 한데 너무 문제를 어렵게 생각해서 못풀었던 것 같다. 그때나 지금이나 원리는 비슷한데 한 끗의 차이 때문에 맞고 틀림이 결정되었다.

어차피 최대의 이윤을 내려면 전시품들이 키 순서대로 있어야 한다. 먼저 키 순대로 정렬하고 크기 차이가 S이상 나는 전시품들의 부분 집합 중에서 가장 큰 부분 집합을 구하는 것이 문제 푸는 데 핵심이다.

위 문제는 DP로 해결 할 수 있다. 키 순서대로 하나 하나씩 차근차근 풀어가면 된다. 알고리즘 순서도는 다음과 같다.

1. 내가 i 번째 그림을 체크 한다고 하자. 

2. i번째 그림과 크기 차가 S이하로 나는 그림들 중(j까지라 하자)에서 지금까지 나온 가장 최고의 이윤을 확인 한다.

3. i번째 그림의 가격과 j의 범위 까지 최고의 이윤의 값을 더하면 그 그림까지 샀을 때 최고의 이윤을 확인 할 수 있다.

이전에 어떤 그림들이 포함되었는지 알 필요가 없으며 단지 최대의 값만 확인하면 된다.

어차피 탐색하는 그림의 크기는 계속 증가하므로 이 전의 그림들을 탐색할 필요는 없다는 원리를 두어서 O(1)에 해결 할 수 있다.

알고리즘의 시간 복잡도는 O(N)

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct Picture{ int height, cost; }; Picture picture[300005]; int d[300005]; bool compare(Picture a, Picture b){ if(a.height == b.height) return a.cost > b.cost; else return a.height < b.height; } int main(){ int N, S; int res = 0; int find=0; int curmax=0; scanf("%d %d", &N, &S); picture[0].cost=0; picture[0].height=0; for(int i=1; i<=N; i++){ scanf("%d %d", &picture[i].height, &picture[i].cost); } sort(&picture[0], &picture[N+1], compare); for(int cur=1; cur<=N; cur++){ for(; find < cur && picture[cur].height-picture[find].height >= S; find++){ curmax = max(curmax, d[find]);} d[cur] = picture[cur].cost + curmax; res = max(res, d[cur]); } printf("%d\n", res); return 0; }