[백준] 2419 - 사수아탕 (c++)

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

문제 요약

n개의 사탕바구니 위치가 주어진다. 각 사탕 바구니에 사탕이 m개 씩 들어있다. 아직 먹지 않은 사탕 바구니에 사탕이 1시간당 1개씩 녹는다. 1이동 하는데 1시간이 들때, 0에서 시작해서 먹을 수 있는 최대 사탕 개수를 구해라.

 

풀이 (N^3)

• DP

dp배열은 dp[n][n][2];  dp[i][j][isr] i번 부터 j번 바구니까지 모두 먹었고 현재 위치가 isr==false면 i 아니면 j 이렇게 구성한다. 현재까지 혹은 현재부터 먹을 사탕을 최대화하는 문제로 보기 쉬운데 경과시간을 모르기 때문에 그렇게 해선 최적으로 만들 수 없다. 발상의 전환이 필요한데 바로 녹을 사탕 개수를 최소화 하는 것이다. 그렇다면 녹을 사탕 개수를 구하는 방법이 관건인데 dp를 돌리기 전 부터 먹을 사탕 개수 k를 미리 정해두면 가능하다. i~j를 통해 먹은 바구니 개수를 알 수 있기 때문에 (k-먹은 개수)*거리개의 사탕이 녹는다는 것을 구할 수 있다. m*k-녹을 사탕 최소개수로 답까지 구할 수 있다.

 

업데이트는 i->j 거리를 저장하는 배열을 미리 만들어서 O(1)에 할 수 있고 먹은 바구니 개수는 i~j로 매번 계산하는 것이 아니라 Dp 재귀에 인자로 넘기면 된다. 그러면 Dp배열 한 번 채우는 걸 n^2에 할 수 있게 되어 1~n를 k값으로 모두 돌려볼 수 있다.

 

바구니가 0에 존재할 경우를 따로 처리해줘야 한다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mid (st+en>>1)

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;cin>>n>>m;
    int ogn=n;
    vector<int> ar(n);
    bool isz=0;
    for(auto&x:ar) {
        cin>>x;
        if(x==0)
            isz=1;
    }
    if(!isz)
        ar.push_back(0),n++;
    sort(all(ar));
    ar.insert(ar.begin(),0);
    vector<vector<ll>> co(n+1,vector<ll>(n+1,0));
    for(int i=1;i<=n;i++) 
        for(int j=i+1;j<=n;j++)
            co[i][j]=co[i][j-1]+ar[j]-ar[j-1];
    vector<vector<vector<ll>>> dp(n+1,vector<vector<ll>>(n+1,vector<ll>(2,1e18)));
    function<ll(int,int,bool,int)> Dp = [&](int l,int r,bool isr,int c)->ll {
        if(c==0)
            return 0;
        ll& ret=dp[l][r][isr];
        if(ret!=1e18)return ret;
        int u=(isr?r:l);
        if(l>1)
            ret=Dp(l-1,r,0,c-1)+co[l-1][u]*c;
        if(r<n)
            ret=min(ret,Dp(l,r+1,1,c-1)+co[u][r+1]*c);
        return ret;
    };
    ll ans=-1e18;
    int st=find(ar.begin()+1,ar.end(),0)-ar.begin();
    for(int i=0;i<=ogn;i++) {
        for(auto&x:dp)
            for(auto&y:x)
                for(auto&z:y)
                    z=1e18;
        ans=max(ans,m*i-Dp(st,st,0,i));
    }
    cout<<ans+(ogn==n?m:0);
}