PS와 개발을 공부하자

BOJ 5977번 Mowing the Lawn 본문

Algorithm/Problem Solving

BOJ 5977번 Mowing the Lawn

sgc109 2017.08.07 16:07

문제 링크


N <= 10^5, K <= N

이 문제는 N 이 주어지고 N개의 정수가 주어진다.

N개의 정수 중에 일부만 골라서 합을 최대로 만들어야 하는데

K개를 초과하여 연속된 수를 고를 수가 없다는 제약이 있을 때 최대 합을 구하는 문제이다.

우선 dp 로 부분문제를 정의하고 점화식을 세워보자.


psum[i] : 1~i 번째 수의 합

dp[i] : i 까지 봐줬을 때 최대 합

dp[i] = max(psum[i] - psum[j] + dp[j - 1]) ( i - K <= j <= i )

점화식을 좀 설명하자면 마지막으로 연속된 [j + 1, i] 구간을 선택했고 j번째 수는 선택하지 않았으며

j - 1 번째 수까지는 재귀적으로 최대값을 취하는 것이다.

마지막에 아예 선택하지않는 것도 포함되어있다는 것에 유의.

그럼 일반적인 방법으로는 O(N^2) 이 걸릴 것이다. 그런데 여기선 N 이 커서 안된다.


우선 위의 점화식을 살짝 바꿔보자.

잘 보면 j만 변하는 것이기 때문에 psum[i] 는 공통된 값이라는 것을 알 수가 있고 이것을 밖으로 빼보면 결국

dp[i] = psum[i] + max(dp[j - 1] - psum[j]) (i - K <= j <= i) 라는 것을 알 수가 있다.

그럼 결국 마지막에 연속된 K개의 어떤 값중에 최대만 유지해주면 된다는 것이 핵심이다.

multiset 과같은 자료구조를 사용해도 되지만 이러면 로그가 붙고 

여기서 덱을 사용하면 O(N) 으로 줄일 수가 있다.  그런데 비슷한 문제를 어디서 본 것같다.

여기를 보고오자. 결국 C[j] = dp[j - 1] - psum[j] 라고 정의해보면 저 문제와 정확히 같다는 것을

알 수가 있다. 그럼 끝!


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
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
ll psum[100003];
ll A[100003];
ll dp[100003];
deque<int> dq;
int N, K;
ll C(int i){
    return dp[i - 1- psum[i];
}
int main() {
    fastio();
    cin >> N >> K;
    for(int i = 1 ; i <= N; i++cin >> A[i];
    for(int i = 1 ; i <= N; i++) psum[i] = psum[i - 1+ A[i];
    for(int i = 1; i <= N; i++){
        while(!dq.empty() && dq.front() < i - K) dq.pop_front();
        while(!dq.empty() && C(dq.back()) <= C(i)) dq.pop_back();
        dq.push_back(i);
        dp[i] = psum[i] + C(dq.front());
        if(i <= K) dp[i] = max(dp[i], psum[i]);
    }
    cout << dp[N];
    return 0;
}
cs


'Algorithm > Problem Solving' 카테고리의 다른 글

BOJ 3133번 코끼리  (0) 2017.08.07
BOJ 11003번 최소값 찾기  (0) 2017.08.07
BOJ 5977번 Mowing the Lawn  (0) 2017.08.07
BOJ 10919번 선물 상자  (0) 2017.08.07
Topcoder SRM 537 Div1(Easy) KingXNewCurrency  (0) 2017.08.02
Codeforces Round #424 (Div. 2) E. Cards Sorting  (0) 2017.07.30
0 Comments
댓글쓰기 폼