[백준] 21758 : 꿀 따기

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

21758번: 꿀 따기

---

• 벌통이 가장 왼쪽에 있을 경우, 꿀벌 두마리 중 한마리는 반드시 가장 오른쪽에 위치하는 것이 오른쪽에 있는 꿀들을 전부 가져오기 때문에 최댓값이 된다.
• 이 때, 나머지 한 마리의 위치에 대해서만 최댓값이 되게 설정해주면 두마리의 합이 최대가 된다.
• 마찬가지로 벌통이 가장 오른쪽에 있을 경우도 똑같이 한 마리는 반드시 가장 왼쪽에 위치한다.
• 벌통이 중간 지점에 있을 경우, 꿀벌 두 마리는 반드시 양 극점에 위치하는 것이 최댓값이 된다.
• 어차피 꿀벌의 다음 위치부터 벌통까지의 합을 구해야 하기 때문에, 벌통이 중간에 있을 때 꿀벌 두마리가 같은 방향에 있으면 반대편 꿀들이 무의미해진다.
• 각 지점 별로 누적합 값을 저장해놓은 뒤, 위의 3가지 케이스에 대해서만 검사해준다.

---

#include <iostream>

using namespace std;

int N, temp, answer = 0;
int honey[100000];
int leftc[100000];          // 인덱스 0 부터 i 까지 누적합
int rightc[100000];         // 인덱스 N-1 부터 i 까지 누적합

int main(void)
{
    cin >> N;

    for(int i = 0 ; i < N ; i++)
    {
        cin >> honey[i];
        temp += honey[i];
        leftc[i] = temp;
    }
    for(int i = 0 ; i < N ; i++)
    {
        rightc[i] = temp;
        temp -= honey[i];
    }

    temp = 0;
    for(int i = 1 ; i < N-1 ; i++)  // 통이 가장 오른쪽, 꿀벌 하나는 가장 왼쪽 고정이고 나머지 꿀벌의 위치
    {
        if(leftc[N-1] - leftc[i] - honey[i] > temp)     // 나머지 꿀벌 하나가 갖는 최댓값 확인
        {
            temp = leftc[N-1] - leftc[i] - honey[i];
        }
    }
    answer = max(answer, temp + rightc[0] - honey[0]);

    temp = 0;
    for(int i = N-2 ; i >= 1 ; i--) // 통이 가장 왼쪽, 꿀벌 하나가 가장 오른쪽 고정이고 나머지 꿀벌의 위치
    {
        if(rightc[0] - rightc[i] - honey[i] > temp)     // 나머지 꿀벌 하나가 갖는 최댓갑 확인
        {
            temp = rightc[0] - rightc[i] - honey[i];
        }
    }
    answer = max(answer, temp + rightc[0] - honey[N-1]);

    temp = 0;
    for(int i = 1 ; i < N-1 ; i++)  // 꿀벌 두마리가 양쪽 끝에 고정이고 통의 위치
    {
        if(leftc[i] + rightc[i] > temp)                 // 벌통의 위치에 따른 최댓값 확인
        {
            temp = leftc[i] + rightc[i];
        }
    }
    answer = max(answer, temp - honey[0] - honey[N-1]);

    cout << answer << endl;
}