21758번: 꿀 따기 - 누적 합

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

21758번: 꿀 따기

 

관찰, 알고리즘

꿀통 위치, 두 벌의 위치를 일일이 정하고 꿀의 합까지 구한다면 시간 초과가 날 것이다. 누적 합을 사용한다면 꿀의 합을 빠르게 구할 수 있을 것이다. 그렇다면 꿀통 위치, 두 벌의 위치를 어떻게 구해야 하는가?

 

꿀통 위치가 두 벌 사이에 있지 않다고 가정해 보자. 이때, 꿀통과 어떤 한 벌은 반드시 맨 끝 장소에 있어야 한다. 그렇지 않다면 무조건 꿀 양에서 손실을 볼 수밖에 없다. 나머지 한 벌은 그 사이의 장소에 위치시키며 누적 합을 이용해 최댓값을 구하면 된다.

이번에는 꿀통 위치가 두 벌 사이에 있다고 가정해 보자. 하지만 이 경우는 대개 꿀통 위치가 두 벌 사이에 있지 않을 때보다 작다. 꿀통 위치가 두 벌 사이에 있다면, 두 벌이 공통으로 꿀을 따는 위치는 꿀통 위치밖에 없다. 하지만 꿀통 위치가 두 벌 사이에 있지 않다면, 두 벌이 공통을 꿀을 따는 위치의 수가 전자보다 더 많거나 같을 수밖에 없다.

 

즉 꿀통 위치가 두 벌 사이에 있을 때가 최대가 되기 위해서는 다음 조건을 만족해야 한다.

1. 꿀을 따는 위치의 수가 두 경우에 대해서 같다.

2. 꿀통 위치에 있는 장소의 꿀 양이 양 끝 꿀의 양보다 크다.

이 두 조건을 만족하는 경우는 N = 3이며 꿀의 최댓값이 두 번째 장소일 때일 뿐이다.

 

구현

N = 3이며 꿀의 최댓값이 두 번째 장소일 때만 예외 처리를 해 주고, 나머지 경우에 대해서는 누적 합을 이용해 최댓값을 구하면 된다. 이 과정은 \(O(N)\)내에 충분히 해결할 수 있다.

#include <bits/stdc++.h>
#define inf 1e9
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N;
ll honey[100001];
ll psum[100001];
ll ans{0};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

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

    if (N == 3)
    {
        int mxIdx, mx = 0;
        for (int i{1}; i <= N; i++)
        {
            if (mx < honey[i])
            {
                mx = honey[i];
                mxIdx = i;
            }
        }
        if (mxIdx == 2)
        {
            cout << honey[mxIdx] * 2 << "\n";
            return 0;
        }
    }

    for (int i{2}; i < N; i++)
    {
        ll sum = psum[N] - psum[1] - honey[i];
        sum += psum[N] - psum[i];
        ans = max(ans, sum);
    }
    for (int i{1}; i < N - 1; i++)
    {
        ll sum = psum[N - 1] - honey[i + 1];
        sum += psum[i];
        ans = max(ans, sum);
    }
    cout << ans << "\n";
}

 

참고 : 꿀통 위치가 두 벌 사이에 있다면 두 벌은 무조건 맨 끝 장소에 있을 수밖에 없다. 따라서 꿀통 위치를 배열 내에서 순회하며, 누적 합을 이용해 합을 구해도 \(O(N)\) 내에 수행 가능하므로 이렇게 구현해도 상관없다.

#include <bits/stdc++.h>
#define inf 1e9
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N;
ll honey[100001];
ll psum[100001];
ll ans{0};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

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

    for (int i{2}; i < N; i++)
    {
        ll sum = (psum[N] - psum[1] - honey[i]) + (psum[N] - psum[i]);
        ans = max(ans, sum);
    }
    for (int i{1}; i < N - 1; i++)
    {
        ll sum = (psum[N - 1] - honey[i + 1]) + psum[i];
        ans = max(ans, sum);
    }
    for (int i{2}; i < N; i++)
    {
        ll sum = (psum[i] - psum[1]) + (psum[N - 1] - psum[i - 1]);
        ans = max(ans, sum);
    }
    cout << ans << "\n";
}