프로그래밍

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

[난이도] Silver1
[유형] 누적 합

[풀이]
N개의 장소가 a[1]~a[N] 일 때, 아래 3가지 경우에 대해 각각 계산해보면서 답을 갱신해주면 됩니다.
계산의 시간을 줄이려면 1~N의 누적합을 미리 구해두어야 합니다.

case1) 벌통이 index 1 에 있는 경우
벌 한마리는 index N에 있어야 하고,
나머지 한마리는 어디에 있는 것이 최적인지 알 수 없으므로
2~N-1에 나머지 한마리가 있는 경우 모두를 계산해 줍니다.
누적합을 이용하면 각 경우를 O(1)에 계산이 가능하므로 O(N)에 모든 경우를 계산 가능합니다.

case2) 벌통이 index N 에 있는 경우
벌 한마리는 index 1에 있어야 하고, 나머지 계산은 case1과 동일합니다.

case3) 벌통이 1과 N 사이에 있는 경우
벌은 1과 N에 있는 것이 최적입니다. 벌통을 2~N-1으로 옮겨보면서 계산해줍니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,sum[100001],a[100001],ans;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) {
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=2;i<N;i++) {
        ans=max(ans,2*sum[N]-a[1]-a[i]-sum[i]);
        ans=max(ans,sum[N-1]-a[i]+sum[i-1]);
        ans=max(ans,sum[i]-a[1]+sum[N-1]-sum[i-1]);
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/21758.cpp