[C++] BOJ 2515 - 전시장

 

BOJ 2515 - 전시장

 

BOJ 2515 - 전시장 (https://www.acmicpc.net/problem/2515)

 

01. 🔎 문제 탐색

N: 그림의 개수  $(1 \leq N \leq 300,000)$
S: 판매가능해지는 보이는 부분의 세로 길이  
H, C: (그림의 높이, 그림의 가격)  $(1 \leq S \leq H \leq 300,000)$, $(1 \leq C \leq 1,000)$

01-1. 가능한 시간 복잡도

• 그림의 개수가 최대 300,000개로 시간 복잡도 $O(N log N)$ 이하로 구현되어야 함

01-2. 알고리즘 선택

• 높이가 오름차순으로 정렬된 그림 리스트에서 i번째 그림까지 최대 가격을 저장하고, 각 그림에 대해 이후에 등장할 그림의 높이가 S 만큼 차이가 날 경우, 이전에 저장된 최대 가격을 이용하여 누적 계산할 수 있으므로, DP를 이용
• 각 i번째 그림에 대해 S만큼 차이나는 이전 그림을 선형탐색할 경우, 시간 복잡도 $O(N^2)$으로 TLE가 발생하므로, 슬라이딩 윈도우를 통해 이전 그림들을 관리하는 것으로 S 이상 높이가 차이나는 그림 중, 최대 누적 가격만을 추적할 수 있음
  따라서, 시간 복잡도 $O(N)$ 으로 구현 가능

02. 📝 코드 설계하기

1. 그림의 개수, 높이 제한, 그림의 정보를 입력
2. 그림을 높이 오름차순으로 정렬
3. 1번 그림은 아무 영향을 받지 않으므로, dp[0]에 그림의 가격을 저장
4. 2번 그림부터 N번 그림까지 탐색하며, 이전 그림들에 대해 높이가 S 이상 차이나는 최대 누적 가격을 추적하여,
   가격과 위치를 저장 $\rightarrow$ max_prev, j
   1. max_prev는 S이상 차이가 나는 그림의 나열에서 가장 가격이 높은 상태를 저장
   2. 슬라이딩 윈도우의 시작 위치 j를 조건(현재 그림의 높이와 비교해서 S 이상 차이가 날 때,)을 만족할 때까지 증가
5. 이전 최대 누적 가격과 (max_prev+현재 그림의 가격)을 비교하여 더 높은 가격을 현재 상태에 저장 $\rightarrow$ dp[i]
   
   1. 이전 상태 유지: dp[i-1]
   2. 이전 그림을 골랐을 때 누적합: max_prev + art[i].second
      (max_prev는 이후에 등장하는 높이와 비교해서 항상 S 이상 차이나므로, 가능)
6. 이전의 최대 가격 상태들이 계속해서 누적되어 dp[N-1]이 최종적으로 가장 큰 값을 가지게 됨

03. 🛠️ 시도별 수정

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int N, S, H, C;
  vector<int> dp(3e5+1, 0);
  vector<pair<int, int>> art;

  cin >> N >> S;
  for(int i = 0; i < N; i++){
    cin >> H >> C;
    art.emplace_back(H, C);
  }
  sort(art.begin(), art.end());

  dp[0] = art[0].second;

  int j = 0;
  int max_prev = 0;
  for(int i = 1; i < N; i++){
    while(j < i && art[j].first <= (art[i].first - S))
      max_prev = max(max_prev, dp[j++]);
    
    dp[i] = max(dp[i-1], max_prev + art[i].second);
  }

  cout << dp[N-1] << "\n";

  return 0;
}