BOJ 11001 - 김치

문제 태그 : https://www.acmicpc.net/problem/11001

문제 소개

각 날 별로 넣을 때의 가치와 꺼낼 때의 온도가 주어진다. 어떤 김치의 맛은 (숙성 시간)*(김치를 꺼낼 때의 온도)+(김치를 넣은 날 가치)로 정의된다. 만들 수 있는 가장 맛있는 김치의 맛을 구하여라.

문제 풀이

이 문제를 봤을 때는 이 문제가 DnC Optimization을 쓰는 문제인지 모르고 봤다. (DnC Optimization에 대한 설명글)
그리고 풀이를 들었기 때문에 상세한 의식의 흐름과정은 설명할 수가 없다. 그대신 식을 전개해 나가면서 왜 DnC 적용이 되는지를 살펴보려고 한다. 

넣은 날의 가치를 $V_i$라고 하고, 꺼낼 때의 온도는 $T_i$라고 하자.
나는 j일때 넣은 김치가 제일 맛있을 때 꺼내려면 i일에 꺼내야 된다면, j+1일에 넣은 김치는 i일 또는 그 이후에 꺼내야 된다고 말하고 싶다. 이를 증명하기 위해 j+1일에 넣은 김치가 제일 맛있으려면 i-1일에 꺼내야 한다고 하자. 

j+1일에 넣은 김치가 제일 맛있으려면 i-1일에 꺼내야 한다를 식으로 정리하면 

$V_{j+1}+(i-1-j-1)\times T_{i-1}\geqslant V_{j+1}+(i-1-j)\times T_{i}$ 가 되고, 이를 $T_{i-1}$에 대해 정리하면,

$T_{i-1}\geqslant \frac{i-j-1}{i-j-2}T_{i}$ 이고, 따라서 $T_{i-1}\geqslant \frac{i-j}{i-j-1}T_{i}$이다. 
오른쪽 식을 다시 양변에 $i-j-1$을 곱하고 $V_i$를 더하면, 아래와 같은 식이 나온다.

$V_{j}+(i-1-j)\times T_{i-1}\geqslant V_{j}+(i-j)\times T_{i}$
이는 j일에 넣은 김치도 i-1일에 꺼내는 것이 더 맛있다는 것이고, 이는 조건과 모순된다. 따라서 j일때 넣은 김치가 제일 맛있을 때 꺼내려면 i일에 꺼내야 된다면, j+1일에 넣은 김치는 i일 또는 그 이후에 꺼내야 된다.

이 조건은 DnC Optimization를 쓸 수 있는 조건이 되고, 쓰면 $O(NlgN)$에 문제를 해결할 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
ll t[1010101];
ll v[1010101];
ll n,d;
ll ans;
 
void kimci(ll s,ll e,ll is,ll ie)
{
    ll i,j,k,l,mid=(s+e)/2;
    ll maxi=0,id=0;
    ll lo=max(mid,is);
    ll hi=min(mid+d,ie);
    for(i=lo;i<=hi;i++)
    {
        if( (i-mid)*t[i]+v[mid]>maxi )
        {
            maxi=(i-mid)*t[i]+v[mid];
            id=i;
        }
    }
    ans=max(ans,maxi);
    if(s!=mid) kimci(s,mid-1,is,id);
    if(e!=mid) kimci(mid+1,e,id,ie);
}
 
int main()
{
    ll i,j,k,l,m;
    scanf("%lld %lld",&n,&d);
    for(i=1;i<=n;i++)
        scanf("%lld",&t[i]);
    for(i=1;i<=n;i++)
        scanf("%lld",&v[i]);
    kimci(1,n,1,n);
    printf("%lld",ans);
}