C++ / 백준 / 21758 / 꿀 따기

문제

 

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

21758번: 꿀 따기

문제풀이

 

벌은 항상 2마리 이고 벌통은 하나이다.

3가지 경우를 나눠 계산했다.

 

*벌은 노란색으로, 벌통은 회색으로 표시

 

1) 벌이 양옆 끝에 하나씩 있는경우

왼쪽 벌은 2 + 3, 오른쪽 벌은 3 + 4 + 5 의 꿀을 얻는다.

간단하게 식으로 모든 꿀의 합 - (왼쪽 벌꿀 + 오른쪽 벌꿀) + 벌통 꿀 으로 표현할 수 있다.

모든 경우를 탐색해야 하므로 반복문을 통해 꿀통을 1칸부터 끝전칸까지 이동하며 최댓값을 구해준다.

 

 

2) 벌통이 맨 오른쪽에 있고, 벌이 나머지칸에 있는 경우

왼쪽 벌은 2 + 4 + 5 + 6, 오른쪽 벌은 4 + 5 + 6 의 꿀을 얻는다.

왼쪽벌은 총합에서 0번 꿀만 빼면 되고, 오른쪽 벌은 앞의 모든 꿀을 빼야한다.

따라서 왼쪽부분의 꿀을 누적합하여 구하고, 총합에서 누적합된 꿀을 빼면 된다.

 

3) 벌통이 맨 왼쪽에 있고, 벌이 나머지칸에 있는 경우 (2와 방향만 반대인 경우)

2와 반대로 왼쪽 벌이 움직여야한다.

오른쪽 벌은 총합에서 6번 꿀만 빼면 되고, 왼쪽벌은 뒤의 모든 꿀을 빼면된다.

이 부분역시 반복문을 돌리면서 누적합을 구하고 빼면된다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX honey.size() -1
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int  N(0), idx(0), sum(0), answer(0);
	int left(0), right(0), wasted_honey(0), bee1(0), bee2(0);
	cin >> N;

	vector<int>honey(N, 0);

	for (idx = 0; idx < N; ++idx) {
		cin >> honey[idx];
		sum += honey[idx];
	}

	for (idx = 1; idx < MAX; ++idx) {
		answer = max(answer, sum - (honey[0] + honey[MAX]) + honey[idx]);
	}

	wasted_honey = honey[0];
	for (right = 1; right < MAX; ++right) {
		bee1 = sum - (honey[0] + honey[right]);
		wasted_honey += honey[right];
		bee2 = sum - wasted_honey;

		answer = max(answer, bee1 + bee2);
	}

	wasted_honey = honey[MAX];
	for (left = MAX - 1; left > 0; --left) {
		bee2 = sum - (honey[MAX] + honey[left]);
		wasted_honey += honey[left];
		bee1 = sum - wasted_honey;

		answer = max(answer, bee1 + bee2);
	}

	cout << answer;
}