[백준OJ] 21758번 꿀 따기

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

21758번: 꿀 따기

---

 

-풀이-

먼저 3가지의 경우로 나누었다.

1) 벌-벌-꿀통

2) 벌-꿀통-벌

3) 꿀통-벌-벌

 

위의 세가지의 경우로 나눌 수 있다.

1번과 3번의 경우, 맨 바깥쪽 벌과 꿀통은 양 끝에 위치하고있어야지 가장 큰 경우가 나온다. 따라서 사이에 있는 벌의 위치를 조절해가며 최댓값을 갱신하면 된다. 이때 최댓값을 갱신할때, 벌꿀의 위치를 포함 하면 안되므로, 1번벌~꿀통+2번벌~꿀통 - 2번벌이 위치한 자리의 꿀값으로 갱신해주어야 한다.

 

2번과 같은 경우, 벌과 벌은 양쪽 끝에 있는상태에서, 꿀통의 위치를 조절해가며 양끝부터 벌꿀통 까지의 누적합이 같은경우를 선택하면 된다. 

 

위의 경우들을 구하기 위해, 왼쪽부터의 누적합과 오른쪽부터의 누적합을 구하여 풀면 된다.

 

-시간복잡도-

누적합과 최댓값을구하는 로직 모두 O(N)이 걸린다.

 

-코드-

 

#include<iostream>
#include<algorithm>
using namespace std;

int n;
int bucket[100002] = { 0 };
int ldp[100002] = { 0 };
int rdp[100002] = { 0 };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> bucket[i];
	}

	for (int i = 1; i <= n; i++) {
		ldp[i] = ldp[i - 1] + bucket[i];
	}
	for (int i = n; i >= 1; i--) {
		rdp[i] = rdp[i + 1] + bucket[i];
	}

	int answer = -1;
	// 벌 벌 꿀통
	for (int i = 2; i < n; i++) {
		answer = max(answer, (ldp[n]-ldp[1]) + (ldp[n] - ldp[i]) - bucket[i]);
	}
	//꿀통 벌 벌
	for (int i = n - 1; i >= 2; i--) {
		answer = max(answer, (rdp[1]-rdp[n]) + (rdp[1] - rdp[i]) - bucket[i]);
	}
	//벌 꿀통 벌
	for (int i = 2; i <= n - 1; i++) {
		answer = max(answer, ldp[i]-bucket[1] + rdp[i]-bucket[n] );
	}


	cout << answer << "\n";
	return 0;
}