BOJ 2515 - 전시장

www.acmicpc.net/problem/2515

2515번: 전시장

 

DP 로 풀어야하는 문제이다.

 

DP 배열을 아래와 같이 정의하면..

 

DP[n] : 첫번째 부터 n 번째 그림까지 비교했을때, 판매 가능한 그림 가격의 최대합

 

n 번째 그림을 무조건 전시한다고 가정했을때, n 번째 그림 보다는 앞에 있는 그림 중 가장 높이가 높은 것의 정보를 temp[n] 에 저장한다.

temp 배열을 초기화할때 주의할점은, 판매 가능한 그림이 되려면 보이는 부분의 세로 길이가 S 이상이어야 하므로, 이전 그림을 나타내는 arr[temp[i]].first 와 현재 i 번째 그림을 나타내는 arr[i].first 간의 차가 S 이상일 경우만 걸러내야한다.

그리고 경우의 수를 하나씩 늘리면서 temp 배열을 초기화 하기 때문에, N = 1 일 경우 답이 안맞을 수 있으므로 반복문 끝날때 하나씩 빼준다.

 

그리고 dp 배열을 채우는 방법은

dp 배열이 의미하는것이 위에서, 1 ~ N 번째 그림까지 비교했을때, 판매 가능한 그림 가격의 최대합이라 했다

이는 n 번째 그림을 전시했을때, 최대값 (dp[temp[n]] + arr[n].second => n 번째, 그림을 전시하고 앞에 것도 고려한 경우)

그리고 n 번째 그림을 전시하지 않았을때의 최대값 이렇게 두가지 경우로 나뉠 수 있다 

(그러므로, dp[i] = max(dp[i], dp[i - 1]) 을 한다) 

 

 

 

- C++

#include <bits/stdc++.h>
 
#define MAX 300001
 
using namespace std;
 
int N, S; // 그림 갯수, 판매 가능한 세로 길이 
int dp[MAX]; // dp[n] : 1 ~ n 번째 그림 비교시에 판매 가능한 그림의 최대값 
int temp[MAX]; // temp[n] : n 번째 그림을 전시했을때 그 보다 앞에 전시한것중 가장 높은 그림 
pair<int, int> arr[MAX]; // 높이, 가격
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> S;
    
    for (int i = 1; i <= N; ++i) 
        cin >> arr[i].first >> arr[i].second;
        
    sort(arr + 1, arr + N + 1);
    
    for (int i = 1; i <= N; ++i) {
        temp[i] = temp[i - 1] + 1;
        while(temp[i] < i) {
            if (arr[i].first - arr[temp[i]].first < S) break;
            temp[i]++;
        }
        temp[i]--;
    }
    
    for (int i = 1; i <= N; ++i) {
        dp[i] = dp[temp[i]] + arr[i].second;
        dp[i] = max(dp[i], dp[i - 1]);
    }
    
    cout << dp[N];
    
    return 0;
}