[C++] 15678 - 연세워터파크 (플래티넘5)

1. 문제 설명

 

15678번: 연세워터파크

연세대 이러고 노니..?

---

2. 아이디어

 

보자마자 dp인 건 이제 감으로 알겠는데, 아무리 생각해도 타임 오버가 날 것 같았다.

그렇다면 다른 자료구조를 섞어 써야 한다는 말인데..찾아보니 세그먼트 트리나 단조 큐를 쓰라고 한다.

 

..? 단조 큐를 여기서요...??

 

대체 여기 어디에 덱을 쓸만한 구석이 있다 한참을 분석해본 결과 개요는 다음과 같다.

관점을 '건너 간다'가 아니라 '건너 온다'라고 바꾸었더니 술술 풀렸다.

입력값을 차례로 받으면서 3가지를 확인한다.

1.  dq.front()의 범위가 현재 위치에서 유효한가?
2.  input 값과 dq.back()의 최적해 + input 값 중 무엇이 더 큰가? (좌로 이동할 것인지 말 것인지)
3.  최종적으로 결정된 최적해의 값이 dq.back()의 최적해보다 크거나 같은가?

이렇게 하면 시작 지점을 지정하지 못 하지 않을까 싶지만 어차피 왼쪽에서 오른쪽으로 이동하나, 오른쪽에서 왼쪽으로 이동하나 결국 값은 같다.

그렇다면 이동할 것인지 말 것인지만 판단하면 된다.

만약, 중간 쯤에서 이동할 필요성이 없어진다면 덱이 한 번 비워졌다가 다시 채워질 것이다.

간만에 꽤 재밌는 문제를 찾아서 즐거웠다.

 

---

3. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

#define ll long long
using namespace std;
typedef pair<int, ll> pil; 

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int N, D; cin >> N >> D;
    deque<pil> dq;
    ll ret = -1e15;

    for (int i=0; i<N; i++) {
        pil cache; cache.first = i; 
        cin >> cache.second;

        while (!dq.empty() && dq.front().first < i - D) 
            dq.pop_front();
        if (!dq.empty())
            cache.second = max(cache.second, dq.front().second + cache.second);
        while (!dq.empty() && dq.back().second <= cache.second)
            dq.pop_back();
        ret = max(ret, cache.second);
        dq.push_back(cache);
    }
    cout << ret << endl;
    return 0;
}