[BAE/<JOON> 문제풀이] 15678. 연세워터파크 / 11003. 최솟값 찾기

https://www.acmicpc.net/problem/15678

15678번: 연세워터파크

https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

서론

서로 완전히 같은 로직으로 풀어서 그냥 같이 올린다. 티어도 사이좋게 플5로 똑같다. 

최소 최대 조건만 다르고 입력까지 똑같아서 그냥 같은 문제다. 풀이는 워터파크를 기준으로 작성했다.

여러가지 풀이들이 있는 것 같은데 나는 prioirty_queue를 가장 많이 쓰기도 하고 코드가 짧아서 이걸로 풀었다.

풀이

사실 문제의 점화식 자체는 매우 간단하다.

• DP[i] = max(DP[i - d ~ i - 1], 0) + arr[i] 

하지만 저 최댓값을 구하는 로직은 O(N)이고 n개의 구간에 대해서 연산하면 O(N^2)이다. 뭔가 다른 방법을 찾아야 한다.

저 검사식을 순차적으로 검사하면 가장 마지막 요소가 제거되고 현재 요소가 새로 추가된다. 중간에 있는 값들은 모두 중복 계산에 들어간다는 것이다. 

 

 예를 들어 구간 크기가 3이고 첫 검사 구간이 1 2 3 이었다면 그 다음 검사는 2 3 4로 1이 제거되고 4번이 들어오는 식으로 n 까지 검사하게 된다. 구간 양 끝값을 제외한 값들을 검사하게 된다면 한 요소당 구간 크기만큼 검사하게되는 꼴이다.

이 부분을 최적화해 TLE를 회피할 수 있다.

 

이를 회피하기 위해 우선순위 큐를 사용했고, 느린 업데이트 방식을 사용했다.

• pq의 top을 꺼내 점화식을 계산한다. 단, 그 요소의 인덱스가 구간을 벗어났으면 pop하고 다음 top을 꺼낸다. 구간 내에 있는 요소가 나올 때 까지 반복한다. pq가 비었을 경우 arr[i] 로 연산한다.
• 점화식을 계산한다.
• 현재의 최적값을 pq에 인덱스와 함께 삽입한다.

pq에 들어갈 수 있는 요소의 개수는 최대 n개 이고 pop / push 연산만 수행하므로 전체 복잡도는 O(n log n) 이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
using ull = long long;
struct dk {
    ull i, v; 
};
struct cmp {
    bool operator()(dk a, dk b) {
        return a.v < b.v;
    }
};
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k; vector<ull> arr(n + 1); vector<ull> dp(n + 1); priority_queue<dk, vector<dk>, cmp> pq;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }        
    ull mx = -10e10;
    for (int i = 1; i <= n; i++) {
        ull s = i - 1 >= k ? i - k : 1;
        while (!pq.empty() && pq.top().i < s) pq.pop();
        s = 0;
        if (!pq.empty()) {
            s = pq.top().v;
        }
        dp[i] = s + arr[i] > arr[i] ? s + arr[i] : arr[i];
        mx = mx > dp[i] ? mx : dp[i];
        pq.push({ i, dp[i] });
    }
    cout << mx;
    return 0;
}