15673-헤븐스 키친 2

15673-헤븐스 키친 2

N개의 수들이 주어지고, 이 N개의 수들을 2개로 그룹지어서 2개의 그룹의 곱이 최대가 되도록 만들면 된다. (그룹의 가중치 = 그룹에 속한 수들의 합)

N=10만이므로, N^2 풀이는 당연히 불가능하다.

우선 테스트케이스에서 99가 나오는 원리이다. 1,2,3 번째에서 -11, 5번째에서 -9를 선택하면 곱이 99가 되고, 이 값이 최대이다.

l_max[],l_min[]배열은 왼쪽부터 보면서 누적합을 계산해 나간다. 여기서 max[]배열은 양수만 고려하므로 만약 누적합이 0보다 작아진다면 차라리 그 수를 선택하지 않는것이 더 나은 선택이므로 0이 된다. min[]배열 또한 같은 원리로 누적합이 0보다 커진다면 그냥 0으로 둔다. 그리고 maxS는 이러한 max 배열들 중에서 지금까지의 가장 큰 값을 저장하는 배열이다. 여기서 색깔이 입혀진 이유는 아래에 곧 나온다.

같은 원리로 r배열은 오른쪽에서부터 왼쪽까지 배열을 채워넣는다.

이제 l배열과 r배열에서 노란색으로 칠해진 칸을 볼 것이다. 왼쪽부터 한칸씩 보면서 빨간색 막대를 기준으로 l_max[]배열은 작대기 왼쪽에서 가장 큰 값, 작대기 오른쪽에서는 r_maxS[]배열에서 가장 큰 값을 찾아서 곱해간다.

이제 max배열(양수)과정이 끝나고 이번에는 min배열(음수)을 볼 것이다. 방법은 방금과 같다.

이렇게 되면 (음수)*(음수)인 99가 최종 답이 된다.

이 풀이가 가능한 이유는 l_max배열은 왼쪽에서부터 누적합이 가장 큰 그룹의 가중치를 저장하고, r_maxS배열은 오른쪽에서부터 누적합이 가장 큰 그룹의 가중치를 저장하므로 특정 경계선(위 그림에선 빨간색 막대)를 정하고 그 경계의 양쪽에서의 값을 서로 곱하면 결과적으로 왼쪽에서의 가중치와 오른쪽에서의 가중치의 곱의 최대를 구한게 된다.

사소한 예외처리로는, N=2일때는 답이 반드시 (첫번째 값) * (두번째 값) 이 되도록 처리해주어야 한다. 그렇지 않으면 위에서 max[],min[] 배열들의 값을 채울 때, 값이 0이 넘어가느냐 마느냐에 따라서 임의로 0으로 채워주었으므로 답이 0이 나올수도 있다. 예를 들어

2

-3 3

이라는 데이터는 반드시 -9가 나와야 한다.

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
#define SIZE 1000009
 
int l_max[SIZE],r_max[SIZE],l_min[SIZE],r_min[SIZE],arr[SIZE];
int l_maxS[SIZE],r_maxS[SIZE],l_minS[SIZE],r_minS[SIZE];
 
int main(){
    int n;    scanf("%d",&n);
 
 
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
    }
 
    for(int i=1 ; i<=n ; i++){
        l_max[i]=max(0,l_max[i-1]+arr[i]);
        l_maxS[i]=max(l_maxS[i-1],l_max[i]);
 
        l_min[i]=min(0,l_min[i-1]+arr[i]);
        l_minS[i]=min(l_minS[i-1],l_min[i]);
    }
 
    for(int i=n ; i>=1 ; i--){
        r_max[i]=max(0,r_max[i+1]+arr[i]);
        r_maxS[i]=max(r_maxS[i+1],r_max[i]);
 
        r_min[i]=min(0,r_min[i+1]+arr[i]);
        r_minS[i]=min(r_minS[i+1],r_min[i]);
    }
    
    ll ans=0;
    if(n==2) ans=(ll)arr[1]*arr[2];
    for(int i=1 ; i<=n && n!=2; i++){
        ans=max(ans,(ll)l_max[i]*r_maxS[i+1]);
        ans=max(ans,(ll)l_min[i]*r_minS[i+1]);
    }
 
    printf("%lld\n",ans);
    return 0;
}