[백준-21758] 꿀 따기

경우를 잘 나눠야 하는 문제이다. 일단 문제의 시간제한 1초를 봤을 때 10만의 입력값으로 통과하기 위해서는 답은 O(Nlog(N)) 의 시간 제한으로 풀 수 있어야 한다. 때문에 이분탐색, 세그먼트 트리 등등의 알고리즘을 떠올릴 수 있다.

이 문제의 경우에는 다른 자료구조가 필요한 것이 아니라 전체 경우가 최대값을 가지기 위해서는 특정 경우로 나뉜다 정도만 알면 풀 수 있다.

전체 최대값을 가질 수 있는 경우는 다음과 같다.

1. "벌꿀 - 벌 - 벌" 순서로 있는 경우
2. "벌 - 벌 - 벌꿀" 순서로 있는 경우
3. "벌 - 벌꿀 - 벌" 순서로 있는 경우

각 경우마다 왼쪽 끝, 오른쪽 끝에 위치해야하고, 중간 특정 지점이 위치해야 한다.

위 3가지 경우에 대해 값을 다 확인하며 최대값을 구할 때 O(N) 의 복잡도를 이끌어 내기 위하여 누적합을 왼쪽, 오른쪽 방향으로 구해놓아야 한다. 그 후에는단순 선형탐색을 통해 답을 빠르게 구할 수 있다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
int arr[100001];
int r_sum[100001];
int l_sum[100001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        l_sum[i] = (i == 0) ? arr[i] : l_sum[i-1] + arr[i];
    }
    for (int i = n - 1; i >= 0; i--)
        r_sum[i] = (i == n-1) ? arr[i] : r_sum[i+1] + arr[i];
    

    int _max = 0;
    for (int i = 1; i < n - 1; i++) 
        if(_max < arr[i]) _max = arr[i];
    
    int answer = 0, a_res, c_res;
    for (int i = 1; i < n - 1; i++) {
        a_res = 0;
        // 오른쪽 끝이 벌꿀인 경우
        a_res += r_sum[i] - arr[i];
        a_res += r_sum[0] - arr[0] - arr[i];
        answer = max(answer, a_res);
				
				// 왼쪽 끝이 벌꿀인 경우
        c_res = 0;
        c_res += l_sum[i] - arr[i];
        c_res += l_sum[n - 1] - arr[n - 1] - arr[i];
        answer = max(answer, c_res);
    }

		// 가운데에 벌꿀이 있는 경우
    cout << max(answer, l_sum[n - 1] - arr[0] - arr[n - 1] + _max);
    
    return 0;
}

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

21758번: 꿀 따기