[백준][C++] 21758: 꿀 따기

문제

풀이

그리디, 누적 합, 많은 조건 분기 문제이다. 

 

N의 최대가 10000이므로 O(N * N)으로는 100점이 불가능하다. 

 

꿀을 가장 많이 채집할 수 있는 경우는 밑의 세 가지이다. 

• 벌집이 가운데 어딘가에 있고, 벌이 가장 왼쪽, 오른쪽에 위치하는 경우
• 벌집이 가장 왼쪽에 있고, 한 벌은 가장 오른쪽, 한 벌은 가운데 어딘가에 위치하는 경우
• 벌집이 가장 오른쪽에 있고, 한 벌은 가장 왼쪽, 한 벌은 가운데 어딘가에 위치하는 경우

벌집이 가장 왼쪽 혹은 오른쪽에 위치하는 경우, 한 벌이 벌집과 가장 멀리있는 것이 꿀을 채집하는데 가장 유리하다(최선의 선택). 

채집한 꿀을 계산할 때, 누적 합이 사용된다. 

코드

#include <iostream>

using namespace std;

int sum[100001];
int honey[100001];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

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

    int answer = 0;

    // 문제의 답은 밑의 종류 중 하나이다.
    // 벌집이 가운데 어딘가에 있고, 벌이 양측에서 접근하는 경우
    // 벌집이 1, N 둘 중 하나의 위치에 있고, 한 벌은 벌집의 반대편, 한 벌은 가운데 어딘가에 위치하는 경우
    // 벌집이 1, N 둘 중 하나의 위치에 있을 때, 한 벌은 가장 반대편에 있는게 제일 유리하다.

    // 벌 - 꿀통 - 벌
    for (int hive = 2; hive < N; ++hive)
    {
        int current = (sum[hive] - honey[1]) + (sum[N - 1] - sum[hive - 1]);
        answer = max(answer, current);
    }

    // 꿀통 - 벌 - 벌
    for (int bee = 2; bee < N; ++bee)
    {
        int current = (sum[bee - 1]) + (sum[N - 1] - honey[bee]);
        answer = max(answer, current);
    }

    // 벌 - 벌 - 꿀통
    for (int bee = 2; bee < N; ++bee)
    {
        int current = (sum[N] - sum[bee]) + (sum[N] - honey[1] - honey[bee]);
        answer = max(answer, current);
    }

    cout << answer;

    return 0;
}