2515 전시장

백준 2515 전시장 https://www.acmicpc.net/problem/2515

문제가 좀 까다로워 보인다. 그림을 배치하는데 세로 기준으로 보이는 부분이 S이상인 것에 대해서만 구입을 해서 최대화 시켜야한다. N의 범위또한 상당히 크다.

하지만 문제를 단순화 시키면 풀만한 문제이다.
사실상 그림이 가려진다는것은 그 그림을 배치하지 않는다는것과 동치이다.

따라서 그림을 높이순으로 오름차순, 가격을 내림차순으로 정렬한 후 [1, N] 구간의 그림을 선택하는 문제로 바뀐다.

DP를 적용시키고 높이 차이가 S이상인 지점을 찾는것은 이분탐색으로 찾으면 된다.

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct Paint{     int v, h; }; bool cmp(const Paint &a, const Paint &b){     if (a.h == b.h)         return a.v > b.v;     return a.h < b.h; } Paint paint[300001]; int N, S; int dp[300001][2];     int diff[300001]; int binary_search(int n){     int l = 0, r = n - 1;          while (l <= r){         int mid = (l + r) / 2;         if (paint[n].h - paint[mid].h >= S) l = mid + 1;         else r = mid - 1;     }     return r; } int main(){     scanf("%d%d", &N, &S);     for (int n = 1; n <= N; n++)         scanf("%d%d", &paint[n].h, &paint[n].v);       sort(paint + 1, paint + N + 1, cmp);     paint[0].h = paint[0].v;       for (int n = 1; n <= N; n++){                 if (paint[n].h - dp[n - 1][1] >= S){            //차이가 S이상일때는 바로 더함             dp[n][0] = dp[n - 1][0] + paint[n].v;             dp[n][1] = paint[n].h;         }         else{             int prev;        // n과의 높이 차이가 S이상인 지점             prev = binary_search(n);             if (dp[n - 1][0] > dp[prev][0] + paint[n].v){ //현재 그림과 더했지만 유지되는 가치가 더 클 때                 dp[n][0] = dp[n - 1][0];                 dp[n][1] = dp[n - 1][1];             }             else{                                         //현재 그림과 높이차이가 가장 작게나는 가치가 더 클 때                 dp[n][0] = dp[prev][0] + paint[n].v;                 dp[n][1] = paint[n].h;             }         }     }     printf("%d\n", dp[N][0]);     return 0; } Colored by Color Scripter

cs