[BOJ/백준][Gold2] 2515 : 전시장 (C++)

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

2515번: 전시장

 

 

[난이도] Gold2
[유형] DP

[풀이]
높이순으로 정렬해놓고 어떤 그림들을 빼야 효율적인지를 정해야 한다.
일일히 구해보면 시간초과가 나므로 메모제이션을 이용해야 한다.
DP[i] : i~N-1번째 그림들에서 얻을 수 있는 최댓 값.

i번 그림은 포함될수도 있고, 제거(제일 뒤로 보내기)할 수도 있다.
1) 포함되는 경우.
만약 i번 그림이 포함된다면 p=(i번 그림의 높이 + S)보다 낮은 그림들은 가려져서 포함될 수 없다.
그러므로 p보다 높이가 높은 가장 작은 index를 k라고 했을 때,
(i번 그림의 가격 + DP[k])이 첫번째 케이스의 결과이다.

2) 포함되지 않는 경우.
i번 그림이 아무것도 가리지 않게 되므로 DP[i]==DP[i+1]이므로
DP[i+1]이 두번째 케이스의 결과이다.

=> DP[i] = 1,2케이스 중에 더 큰 값.

Top-Down 방식으로 구현하였다.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,S,dp[300000],h[300000];
pair<int,int> a[300000];
int sol(int n){
    if(n>=N) return 0;
    int& ret=dp[n];
    if(ret!=-1) return ret;

    int p = a[n].first+S;
    int k = lower_bound(h,h+N,p)-h;
    ret=sol(n+1);
    ret=max(ret,a[n].second+sol(k));

    return ret;
}
int main(){
    scanf("%d%d",&N,&S);
    for(int i=0;i<N;i++) {
        scanf("%d%d",&a[i].first,&a[i].second);
        h[i]=a[i].first;
    }
    sort(h,h+N);
    sort(a,a+N);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/2515.cpp