백준 20181 꿈틀꿈틀 호석 애벌레 - 효율성 혼내주기

 

기능성 문제를 풀고 이 문제를 처음 읽었을때 어떻게 풀지 감이 안잡혔다. 카테고리를 보니 투 포인터가 있어서 공부할때까지 미뤄두었는데, 정작 투 포인터를 공부하고도 엄청나게 헤맸다. 

 

아래의 그림은 예제 입력에 대해 dp 테이블을 채우는 과정이다. cache[n]의 값은 먹이가 n까지 있을 때 얻을수 있는 만족도 최댓값이다.

 

 

[0, 3]까지의 탈피 에너지 최댓값 + [4, 6)의 탈피 에너지 값 = 3 + 9 = 12
[0, 4]까지의 탈피 에너지 최댓값 + [5, 6)의 탈피 에너지 값 = 3 + 7 = 10

 

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

ll psum[100001], cache[100001];
int n, k;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        cin >> psum[i]; psum[i] += psum[i-1];
    }
    
    int s = 1, e = 1;
    ll sum = 0, ans = 0, tmax = 0;
    while(e <= n) {
        sum = psum[e] - psum[s-1];
        if(sum >= k){
            tmax = max(tmax, cache[s-1]);
            cache[e] = max(cache[e], tmax + sum - k);
            s++;
        }
        else e++;
    }
    for(int i = 1; i <= n; ++i){
        ans = max(ans, cache[i]);
    }
    cout << ans;
}