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

문제 링크

21758번: 꿀 따기

문제 요약

N개의 장소가 있다. 이 중 한 곳에는 벌통이, 그리고 추가로 두 곳에는 벌이 존재한다. 벌은 벌통으로 이동하면서 경로상에 있는 꿀들을 모두 채집해간다. 단, 벌이 출발한 곳들의 꿀은 채집하지 않는다. 이때, 얻을 수 있는 꿀의 최댓값을 구해야 한다.

접근 방법

벌통이 양 끝에 있는 경우와, 그 외 칸에 있는 경우, 두 가지 경우로 나눠서 생각했습니다.

벌통이 양 끝에 있는 경우

벌통을 가장 끝에 배치한 순간, 벌 한 마리에 한해서는 무조건 반대쪽 끝에 위치해야 최대한 많은 꿀을 채집할 수 있습니다. 그리고 다른 한 마리인데, 여기서는 좀 다르게 생각해봐야 합니다.

9 9 1 1 ...

위와같은 상황에서 첫번째, 두번째에 벌을 배치하면 첫번째 벌이 오면서 두번째, 9는 채집할 수 없게 됩니다. 하지만 첫번째, 세번째에 벌을 배치하면 9를 채집하고 1을 채집하지 못하게 됩니다. 추가로 두번째 벌이 채집할 수 있는 꿀의 양이 줄었어도 전보다 꿀을 더 많이 채집할 수 있습니다.

여기에 입각해 벌을 한칸씩 이동시켜가면서 손익이 역전되는 순간 반복문을 종료해야 합니다. 다만, 제 경우에는 입력이 10만 정도이기 때문에 두번째 벌을 모든 칸에 배치하는 방법을 써 보았습니다. 이를 벌통이 오른쪽 끝에 있는 경우, 왼쪽 끝에 있는 경우 모두 구현했습니다. 누적합 사용이 필요한데, 워낙 쉽기 때문에 따로 설명은 하지 않겠습니다.

벌통이 그 외 장소에 있는 경우

마지막으로 벌통이 양 끝이 아닌, 가운데의 어딘가에 있는 경우인데, 이 경우에는 무조건 벌을 양 끝에 배치하는 것이 가장 이득입니다. 이제 오면서 꿀을 채집하는데, 벌통이 있는 곳의 꿀은 두 번 채집하기 때문에, 가장 수가 큰 곳에 두는 것이 이득입니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 100001;
int arr[MAX], sum[MAX];

int prefix_sum(int a, int b) { return sum[b] - sum[a - 1]; }

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

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

	int res = 0;
	for (int i = 2; i < n; i++)
		res = max(res, prefix_sum(2, n) + prefix_sum(i + 1, n) - arr[i]);

	for (int i = n - 1; i > 1; i--)
		res = max(res, prefix_sum(1, n - 1) + prefix_sum(1, i - 1) - arr[i]);

	for(int i = 2; i <= n - 1; i++)
		res = max(res, prefix_sum(2, n - 1) + arr[i]);

	cout << res << ' ';
	return 0;
}