[BOJ/C++] 21758: 꿀 따기

🏅 GOLD 5

✏️ 최종 솔루션

1. 각 장소까지의 꿀 누적합 저장
2. 꿀통과 벌의 배치 경우의 수
   1) 꿀통-벌-벌
   최대값을 구하려면 꿀통은 맨 왼쪽, 벌 하나는 맨 오른쪽에 고정하고 중간에 있는 벌을 옮겨가며 최대값 구해야 함
   2) 벌-꿀통-벌
   최대값을 구하려면 벌은 양 끝에 고정하고 중간에 있는 꿀통을 옮겨가며 최대값 구해야 함
   3) 벌-벌-꿀통
   최대값을 구하려면 꿀통은 맨 오른쪽, 벌 하나는 맨 오른쪽에 고정하고 중간에 있는 벌을 옮겨가며 최대값 구해야 함

📌 self feedback

규칙성을 파악하는 것이 어려웠는데 꿀통과 벌을 배치하는 경우의 수를 분류했다면 더 접근하기 쉬웠을 듯
모든 경우의 수를 조합으록 구하는 것이 아니라 꿀통을 고정시키거나 벌을 고정시켰을 때 다른 것들을 어떻게 배치해야 최대값이 나올 수 있는 구조인지 파악했어야 함

✏️ 최종 code

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> honey(n+1);
    vector<int> hsum(n+1);

    for(int i=1;i<=n;i++) {
        cin >> honey[i];
        hsum[i]=hsum[i-1]+honey[i];
    }

    int mx=0;
    // 1. 벌-벌-꿀통
    for(int i=2;i<n;i++) {
        int v=(hsum[n]-hsum[i])+(hsum[n]-honey[i]-honey[1]);
        mx=max(mx,v);
    }

    // 2. 벌-꿀통-벌
    for(int i=2;i<n;i++) {
        int v=(hsum[i]-honey[1])+(hsum[n-1]-hsum[i-1]);
        mx=max(mx,v);
    }

    // 3. 꿀통-벌-벌
    for(int i=2;i<n;i++) {
        int v=(hsum[n-1]-honey[i])+hsum[i-1];
        mx=max(mx,v);
    }

    cout << mx << endl;

}