본문 바로가기

알고리즘 관련/알고리즘&이론

deque를 이용한 다이나믹프로그래밍

BOJ)5977 Mowing the Lawn 라는 문제를 풀 때 이용한 테크닉이다.


문제: icpc.me/5977


시퀀스가 주어질 때 주어진 시퀀스에서 수를 선택하여 최댓값을 만들어야 하는데 수를 연속으로 k이하로 선택가능할 때 답을 출력하는 문제이다.


예를 들어서 n이 5고 k가2라면 (1,2) (4,5) 이런식으로 연속된 수열은 최대 k까지 선택하여야 한다.


문제만 보면 당연히 다이나믹 프로그래밍을 떠올릴 수 있다.


하지만 점화식을 세우다보면 n이 너무 크기때문에 곤란할 수 있다. 하지만 일단 점화식을 세워보자


dp[i]는 i번째 인덱스까지 수열을 처리하였을 때 최댓값이라고 정의를 한다면


dp[i] =max(psum[i]- psum[j]+ dp[j-1]) j:(i-k+1 ~ i) 


라는 수식이 세워진다. 하지만 j의 범위 때문에 dp테이블을 채우려면 n^2의 시간이 필요하다


하지만 조금의 트릭을 사용하여 시간을 줄일 수 있다.


점화식에서 psum[i]는 j값에 영향받지않는 고유한 값이다. 따라서 우리는 j구간중에서 dp[j-1]-psum[j]의 최댓값만 구하면 된다.


이 수식의 j값을 i보다 작기 때문에 dp[i]를 빌드하면서 dp[i-1]-psum[i]를 매번 priority queue에 넣어준다면 굳이 모든 j를 순회하지 않고 가져올 수 있다. 


단 이때 dp[i-1]-psum[i]와 함께 i를 함께 pair형으로 삽입해주어 만약 pq의 최댓값의 인덱스 i가 현재 구간에서 j를 벗어난다면 pop을 해주면 된다. 이는 뒤에 구할 i+1~n에서도 필요없는 구간이기 때문에 지워져도 된다.


따라서 이러한 방법으로 dp를 nlogn에 구할 수 있다.


여기서 pq대신 deque를 이용하면 이를 O(n)에 구할 수 있다.


deque으로 최댓값을 관리하는 방법은 http://jason9319.tistory.com/346을 참고하면 된다.


pq를 이용한 소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
ll n, k, dp[100010], a[100010], p[100010];
int main() {
    scanf("%lld%lld"&n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%lld"&a[i]);
        p[i] = p[i - 1+ a[i];
    }
    priority_queue<pair<ll, ll>> pq;
    pq.push({ dp[0],});
    for (int i = 1; i <= n; i++) {
        while (pq.top().second < i - k) 
            pq.pop();
        dp[i] = p[i] + pq.top().first;
        pq.push({ dp[i - 1- p[i],i });
        dp[i] = max(dp[i], dp[i - 1]);
    }
    printf("%lld\n", dp[n]);
    return 0;
}
cs


deque를 이용한 소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <algorithm>
#include <deque>
using namespace std;
typedef long long ll;
ll n, k, dp[100010], a[100010], p[100010];
deque<pair<ll, ll>> dq;
int main() {
    scanf("%lld%lld"&n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%lld"&a[i]);
        p[i] = p[i - 1+ a[i];
    }
    dq.push_back({ dp[0],});
    for (int i = 1; i <= n; i++) {
        while (dq.size() && dq.front().second < i - k)
            dq.pop_front();
        dp[i] = p[i] + dq.front().first;
        while (dq.size() && dq.back().first < dp[i - 1- p[i])
            dq.pop_back();
        dq.push_back({ dp[i - 1- p[i] ,i });
        dp[i] = max(dp[i], dp[i - 1]);
    }
    printf("%lld\n", dp[n]);
    return 0;
}
cs