[C++] 백준 21758번: 꿀 따기(2021 정보올림피아드 중등부 2교시 1번)

problem

문제링크: https://www.acmicpc.net/problem/21758

입력 : N, 각 장소의 꿀의 양

출력 : 최대의 꿀의 양

solution

두 꿀벌의 위치와 벌통의 위치를 3가지로 나눠 각 경우중 가장 큰 값 출력

1. 벌통이 오른쪽 끝에 있는경우
2. 벌통이 왼쪽 끝에 있는경우
3. 벌통이 두 벌 사이에 있는 경우

code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> a;
vector<int> s;  //subtotal

int main()
{
     int N;
     cin >> N;
     a.resize(N);
     s.resize(N);
     for(int i = 0; i < N; i++){
         cin >> a[i];
     }
     s[0] = a[0];
     for(int i = 1; i < N; i++){
         s[i] = s[i - 1] + a[i];
     }
    
     int ans = 0;
     for(int i = 1; i < N - 1; i++) ans = max(ans, s[i - 1] - a[0] + a[i]);     //벌통이 두 벌 사이에 있을떄
     for(int i = 1; i < N - 1; i++) ans = max(ans, (2 * s[N - 1]) - a[0] - a[i] - s[i]); // 벌통이 오른쪽 끝에 있을때
     for(int i = 1; i < N - 1; i++) ans = max(ans, 2*(s[i - 1]) + s[N - 2] - s[i]);	   //나머지
     

     cout << ans;

     return 0;
}