PS 일기 2024년 1월 29일 (1일 차) (15678번 연세워터파크)

PS 일기 2024년 1월 29일 (1일 차)

PS 일기란?

PS 실력 향상을 목적으로 날마다 푼 문제를 회고하는 것입니다. 문제의 간단한 해법과 함께 어떤 방식으로 접근했는지, 그리고 문제의 해법을 찾는 데 결정적이었던 깨달음은 무엇이었는지 등을 기록합니다.

오늘의 문제

15678번 연세워터파크

알고리즘 분류

• 덱 (Deque)
• DP (dynamic programming)

문제 설명

길이가 $N$ 인 수열의 원소를 아래의 규칙에 따라 방문하여, 방문한 수열 원소들의 합의 최댓값을 찾아야 합니다. 단, 같은 항에 한 번만 방문할 수 있습니다.

1. 시작점 $i (1 \leq i \leq N)$ 에 방문합니다.
2. $j (1 \leq j \leq N, \vert i - j \vert \leq D)$ 에 방문합니다. ($i$ 는 직전에 방문한 항)
3. 방문을 멈추거나 2번으로 되돌아갑니다.

문제 풀이

관측 1

한 방향으로 방문하여도 항상 정답을 구할 수 있습니다.

문제 설명에 따르면 수열을 너무 자유롭게 방문할 수 있습니다. 예를 들어 수열의 길이가 $10$ 이고 $D = 10$ 이라면 $1$ 번째 항에 방문한 후 $10$ 번째 항에 방문한 뒤 $5$ 번째 항에 방문할 수 있습니다. 이처럼 방문할 수 있는 순서가 너무 자유롭다면 탐색하기 힘들어집니다.

수열을 $x, y, z (x \lt z \lt y)$ 의 순서로 방문했다고 합시다. 방문 규칙에 따라 $\vert x - y \vert \leq D, \vert y - z \vert \leq D$ 입니다. 또한 $x \lt z \lt y$ 임으로 $\vert x - z \vert \leq D, \vert z - y \vert \leq D$ 입니다. 따라서 $x, z, y$의 순서로 방문하여도 무방합니다.

관측 2

왼쪽에서 오른쪽으로 방문 할 때 $i (1 \leq i \leq N)$에 마지막으로 방문한 경우 최댓값은 max(0, 이전 D개의 최댓값) + 수열의 $i$ 번째 항입니다.

이제 관측 1을 바탕으로 답을 구해야 합니다. 왼쪽에서 오른쪽 방향으로 방문한다고 할 때 $i (1 \leq i \leq N)$을 마지막으로 방문하였을 때 방문한 수열들의 합의 최댓값은 무엇일까요?

$i$항 이전에 방문한 항 $j (1 \leq j \leq N)$는 $i - d \leq j \leq i$임이 자명합니다. 따라서 $f(i) = i$를 마지막으로 방문하였을 때 방문한 수열들의 합의 최댓값이라면 정의하면 $f(i) = S_i + \max (\max_{k = i - D}^{k \lt i} f(k), 0)$입니다.

구현

의사표현코드

DP[n] = {0, };
For (i = 1; i <= N; i++) {
    // get_max_element(S, i) = S에서 1부터 i번째 요소 중 최댓값을 반환한다.
    DP[i] = max(0, get_max_element(DP, i - 1)) + S[i];
}
ans = get_max_element(DP, N);

이를 Naive하게 구현하면 $O(N \times D)$으로 시간초과가 납니다. get_max_element를 세그먼트 트리, 우선순위 큐 또는 덱을 이용한 최댓값 트릭으로 빠르게 구할 수 있는데, 가장 빠른 덱을 이용한 최댓값 트릭으로 구현하였습니다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = 1e18;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int n, d;
    cin >> n >> d;

    ll ans = -INF;
    deque<pair<ll, int>> dq;
    for(int i = 0; i < n; i++) {
        ll x;
        cin >> x;

        while(!dq.empty() && dq.front().second < i - d) dq.pop_front();
        if(!dq.empty() && 0 < dq.front().first) x += dq.front().first;
        ans = max(x, ans);
        while(!dq.empty() && dq.back().first <= x) dq.pop_back();
        dq.emplace_back(x, i);
    }

    cout << ans;
}