[백준] 15678 - 연세워터파크 (C++)

문제

15678번: 연세워터파크 (acmicpc.net)

15678번: 연세워터파크

 

풀이

오랜만에 만나 본 단조 큐 문제입니다. 단조 큐가 무엇인지는 이곳에서 다루지 않겠습니다.

좌측에서 우측으로 이동하면서, 구간 내의 최댓값을 유지해야 하는 문제이므로 덱을 사용하였습니다.

 

먼저 i - D보다 작은 값들은 모두 제거하여 건널 수 없는 징검다리를 제거합니다.

그리고 지속적으로 현재 dp[i]와 다음 징검다리의 번호를 더한 값(K[i])을 비교하여 최댓값을 dp에 저장합니다.

dp[i]보다 작은 값도 모두 제거합니다. 

 

코드 자체는 굉장히 간결합니다.

#include <algorithm>
#include <deque>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int N, D;
  cin >> N >> D;

  vector<long long> K(N);
  for (int i = 0; i < N; i++) {
    cin >> K[i];
  }

  vector<long long> dp = K;
  deque<pair<long long, long long>> dq;
  for (int i = 0; i < N; i++) {
    while (!dq.empty() && dq.front().first < i - D) {
      dq.pop_front();
    }

    if (!dq.empty()) {
      dp[i] = max(dp[i], dq.front().second + K[i]);
    }

    while (!dq.empty() && dq.back().second < dp[i]) {
      dq.pop_back();
    }
    dq.push_back({i, dp[i]});
  }

  cout << *max_element(dp.begin(), dp.end());

  return 0;
}

 

여담으로, 해당 문제를 풀고 777 문제에 도달하였습니다. Lucky 7!