[BOJ] 15678. 연세워터파크

 

15678번: 연세워터파크

처음에는 아무 생각 없이 그냥 DP로 짰다가... 시간초과가 났다. 당연히 그렇게 쉬울 리가 없을 거라고는 생각했지만 도저히 로직이 생각이 안 나는걸.. 2주동안 이걸 못 풀고 죽어가고 있었는데 이 사람이 풀어주셨다.

---

O(nlogn) 풀이 |

#include <bits/stdc++.h>

using namespace std;

#define INF 987654321987654321

int N, D;
long long a[100000], dp[100000], tree[262144];
void update(int index, int S, int E, int k, long long var)
{
    if (S == E)
    {
        tree[index] = var;
        return;
    }
    if (k <= (S + E) / 2)
        update(index * 2, S, (S + E) / 2, k, var);
    else
        update(index * 2 + 1, (S + E) / 2 + 1, E, k, var);
    tree[index] = max(tree[index * 2], tree[index * 2 + 1]);
}

long long find(int index, int S, int E, int i, int j)
{
    if (i > E || j < S)
        return -INF;
    if (i <= S && j >= E)
        return tree[index];
    return max(find(index * 2, S, (S + E) / 2, i, j), find(index * 2 + 1, (S + E) / 2 + 1, E, i, j));
}

int main()
{
    cin >> N >> D;
    for (int i = 0; i < N; i++)
        cin >> a[i];
    for (int i = 0; i < N; i++)
    {
        dp[i] = a[i];
        dp[i] = max(dp[i], a[i] + find(1, 0, N - 1, max(0, i - D), i - 1));
        update(1, 0, N - 1, i, dp[i]);
    }
    cout << *max_element(dp, dp + N);
}

dp[i]에 들어가는 것은 도착점이 i인 경우의 최대 점수이고, 이 중 답은 모든 dp값 중 최댓값이다.

dp에 값을 넣어가면서 트리를 업데이트하는 구조이기 때문에 처음 트리를 구성할 필요는 없다.

update 함수랑 find 함수만 만들어 준다.

i - D부터 i - 1까지 구간에서의 최댓값을 찾아 a[i]에 더해 dp[i]를 채우는 방식이다.

---

O(n) 풀이 |

#include <bits/stdc++.h>

using namespace std;

int N, D;
long long a[100000], dp[100000];
deque<pair<long long, long long>> q;

int main()
{
    cin >> N >> D;
    for (int i = 0; i < N; i++)
        cin >> a[i];
    for (int i = 0; i < N; i++)
    {
        dp[i] = a[i];
        while (!q.empty() && q.front().first < i - D)
            q.pop_front();
        if (!q.empty())
            dp[i] = max(dp[i], q.front().second + a[i]);
        while (!q.empty() && q.back().second < dp[i])
            q.pop_back();
        q.push_back(make_pair(i, dp[i]));
    }
    cout << *max_element(dp, dp + N);
}

deque를 이용해 배열을 한번 순회하면서, 작은 인덱스의 dp값들을 이용해 현재 인덱스의 dp를 채우는 bottom-up 풀이이다.

dp[i]에 들어가는 것은 도착점이 i인 경우의 최대 점수이고, 덱 안에 들어가는 것은 dp값들의 가장 긴 감소하는 부분수열이다.

dp[i]를 채울 때 고려해야 할 것은 dp[i - D]부터 dp[i - 1]까지이고, dp[i]에 들어갈 것은 그 중 최댓값 + a[i]일 것이다.

덱에는 상기했듯이 감소수열이 들어가고, 즉 덱의 맨 앞 값이 최댓값이므로 그냥 덱의 맨 앞 값을 쓰면 된다.

 

1. 덱의 맨 앞 인덱스가 i - D 보다 작다면 어차피 갈 수 없으니까 뺀다. i는 계속 증가하므로 다시 볼 일 없는 친구들이다.

2. dp[i]에 덱의 맨 앞 값 + a[i]를 넣는다.

3. 덱의 뒤에서 dp[i]보다 작은 값을 모두 빼고, dp[i]를 넣는다. 원래 덱은 가장 긴 감소하는 부분수열이었으므로, 이렇게 해도 가장 긴 감소하는 부분수열이라는 점은 유지된다.

 

배열을 한 번 순회하므로 시간복잡도는 O(n)이다. 이런 방식을 모노토닉 큐(monotonic queue)라고 한다고 한다.

---

느낀 점 |

"참고로 세그트리 dp같은 건 재귀로 풀면 안됩니다"

재귀 그만 좋아해야겠다. 그동안 즐거웠어...