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

문제

아래와 같이 좌우로 $N$개의 장소가 있다.

장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다. 또, 다른 한 장소를 골라서 벌통을 둔다. 아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.

두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다. 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.

두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.
위의 그림과 같이 배치된 경우 두 마리의 벌 모두 $4 + 1 + 4 + 9 + 9 = 27$의 꿀을 따서, 전체 꿀의 양은 54가 된다.

위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은 $9 + 4 + 4 + 9 + 9 = 35$의 꿀을 따고 오른쪽 장소에서 출발한 벌은 $4 + 9 + 9 = 22$의 꿀을 따므로, 전체 꿀의 양은 $57$이 된다.

위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.

장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.

입력

첫 번째 줄에 장소의 수 $N$이 주어진다.

다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.

출력

첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.

제한

 $3 \le N \le 100~000$ 
각 장소의 꿀의 양은 $1$ 이상 $10~000$ 이하의 정수이다.

서브태스크

번호	배점	제한
1	11	$N \le 20$
2	13	$N \le 500$
3	31	$N \le 5~000$
4	45	추가적인 제한이 없음.

예제 입출력

• 예제 입력 1

7
9 9 4 1 4 9 9

• 예제 출력 1

57

• 예제 입력 2

7
4 4 9 1 9 4 4

• 예제 출력 2

54

• 예제 입력 3

3
2 5 4

• 예제 출력 3

10

Solution

#include <iostream>
#include <vector>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> data(N);
    vector<int> sumofData(N);
    for(int i = 0; i < N; i++){
        cin >> data[i];
        sumofData[i] = data[i];
    }
    for(int i = 1; i < N; i++) sumofData[i] += sumofData[i-1];
    int answer = 0;
    for(int i = 1; i < N-1; i++){
        answer = max(answer, 2*sumofData[N-1]-data[0]-data[i]-sumofData[i]);
    }
    for(int i = 1; i < N-1; i++){
        answer = max(answer, sumofData[N-1]-data[N-1]-data[i]+sumofData[i-1]);
    }
    for(int i = 1; i < N-1; i++){
        answer = max(answer, sumofData[i]-data[0] + sumofData[N-1]-sumofData[i-1]-data[N-1]);
    }
    cout << answer << '\n';
}

누적 합이라는 개념을 알아야 쉽게 풀 수 있다.

누적 합은 말 그대로 누적된 수의 합이다.

cin >> N;
vector<int> data(N);
vector<int> sumofData(N);
for(int i = 0; i < N; i++){
    cin >> data[i];
    sumofData[i] = data[i];
}
for(int i = 1; i < N; i++) sumofData[i] += sumofData[i-1];

입력 받은 데이터를의 누적합을 구하는 과정이다. 이 자체로는 $O(N)$ 의 복잡도를 가진다.
왜 이런 작업을 하냐면 구간의 합을 구하기 위해서다.
누적합을 해 두면 편해지는 게 있다면, 예를 들어 0번 인덱스 부터 i번 까지의 합을 구하고 싶다면 누적 합 처리 해둔 배열의 i번째 인덱스를 가져오기만 하면 된다.
어쨌든 for문 돌려서 구하나 미리 구해논거 가져오나 크게 차이는 없다.
중요한건 이 작업을 여러번 해야 한다면 매번 for문을 돌릴 필요가 없어진다는 것이다.

이 문제는 전형적인 누적합 문제다. 어디서 출발해서 어딘가로 도착할 예정인데 그 결과가 지나간 위치의 데이터 합, 즉 누적합을 구하는 문제다.

int answer = 0;
for(int i = 1; i < N-1; i++){
    answer = max(answer, 2*sumofData[N-1]-data[0]-data[i]-sumofData[i]);
}
for(int i = 1; i < N-1; i++){
    answer = max(answer, sumofData[N-1]-data[N-1]-data[i]+sumofData[i-1]);
}
for(int i = 1; i < N-1; i++){
    answer = max(answer, sumofData[i]-data[0] + sumofData[N-1]-sumofData[i-1]-data[N-1]);
}
cout << answer << '\n';

그 후 세 가지 경우를 생각 해 본다.
1. 꿀통이 오른쪽에 있을 때
2. 꿀통이 왼쪽에 있을 때
3. 꿀통이 중간에 있을 때

이 세가지 경우에 대해 for문을 돌리며 최댓값을 구해주기만 하면 된다.
꿀통이 오른쪽에 있다면 당연히 왼쪽 끝에서 부터 진행하는 경우를 생각 해 보아야 한다.
왼쪽이라면 0번 인덱스에서 N번 방향으로 진행하는 경우를 생각해야 한다. 중간이라면 정확히 기분이 있지는 않으니 i 인덱스 기준으로 처리한다.

누적합을 썼기 때문에 이 세가지 경우를 고려하는 상황에서 크게 복잡해지지 않았다. 이를 고려하지 않았다면 매번 합을 구했어야 했을 것이다.