문제

n개의 가게가 줄지어 있다. 이때, 건달이 보호비를 걷는데, 연속한 m개의 업장에서 정확히 k원만 수금한다. 하지만 연속한 m개의 가게가 번 돈의 합이 k원보다 적을 경우에는, 건달은 ‘별 수 없지’를 외치며 합친 금액 만큼만 수금 해간다.(각 가게가 번 돈이 음수가 될 수는 없다.) 또한 맨 앞부분과 맨 뒷부분의 가게들에서는 m개의 가게가 연속하지 않더라도 같은 방법으로 돈을 수금한다. 즉 앞에서 1, … , l번째 가게들을 생각했을 때, l<m이더라도 같은 규칙으로 돈을 수금한다는 것이다. 맨 뒤도 마찬가지 규칙이 성립한다.

자, 이제 각 가게에서 번 돈을 모두 알고 있다고 하자. 어떤 가게에서 얼마만큼 돈을 내는지에 따라, 모든 가게들이 상납하게 되는 돈의 총합이 달라짐을 알 수 있다. 이 때 내게 되는 돈의 최소 값은 얼마인가?

풀이

앞에서부터 greedy하게 채우면 된다는 것은 자명하다. 그리고 덜 채운 칸(모든 돈을 다 쓰지 않은 칸)을 stack으로 관리하면 greedy한 풀이를 쉽게 구현할 수 있다.

문제는 시간복잡도이다. 스택에 한 번 들어간 원소는, 그리디한 알고리즘에 의해 필요할 때 사용되고, 최대 $M$번 들어갔다 나올 수 있다. 하지만 $O(NM)$일 것만 같은 이 풀이가 실은 $O(N)$에 작동한다는 것이 핵심이다.

스택에 들어가고, 나가는 원소를 생각해보자. 새로운 가게를 처음으로 방문할 때(슬라이딩 윈도우가 한 칸 우측으로 이동할 때), 빈 칸은 최대 한 칸 발생할 것이다. 건달이 돈을 걷다가 k원이 채워져서 더 이상 걷을 필요가 없어지는 순간에만 빈 칸이 발생하기 때문이다. 따라서 스택에 원래 있던 것을 포함해서 스택에 들어가는 것은 윈도우가 한 칸 움직일 때 최대 한 번만 발생한다.

스택에 들어가는 원소의 수가 $O(N)$이니, 스택에서 나오는 원소의 수도 $O(N)$이다. 따라서 전체 시간복잡도도 $O(N)$이 됨을 알 수 있다.

코드

#include <bits/stdc++.h>
#define endl '\\n'
#define cediv(a,b) ((a)%(b)==0?((a)/(b)):((a)/(b))+1)
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;

template<typename T>
inline T umax(T &u, T v){return u = max(u, v);}
template<typename T>
inline T umin(T &u, T v){return u = min(u, v);}

ll datas[400020];
ll res[400020];
stack<pair<ll,ll>> blank;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll n,m,k;
    cin>>n>>m>>k;
    for(int i=0; i<n; i++){
        cin>>datas[i];
    }
    ll cnt=0;
    ll cur=0;
    for(int i=0; i<n+m; i++){
        // [i-m,i-1]을 따진다.
        if(i>=m) cur-=res[i-m];
        if(datas[i]>=k-cur){
            res[i]=k-cur;
            cur=k;
            if(res[i]!=datas[i]) blank.push({i,datas[i]-res[i]});
        }
        else{
            ll left=k-cur-datas[i];
            cur=cur+datas[i];
            res[i]=datas[i];
            while(!blank.empty()){
                auto p=blank.top();
                blank.pop();
                if(p.fi<=i-m) break;
                res[p.fi]+=min(left,p.se);
                cur+=min(left,p.se);
                left-=min(left,p.se);
                if(res[p.fi]<datas[p.fi]) blank.push({p.fi,datas[p.fi]-res[p.fi]});
                if(left==0) break;
            }
        }
    }
    for(int i=0; i<n; i++) cnt+=res[i];
    cout<<cnt<<endl;
    return 0;
}