[BOJ/Silver 1] 백준 21758 꿀 따기(C++)

문제 링크

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

21758번: 꿀 따기

 

문제

아래와 같이 좌우로 N개의 장소가 있다.

장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다. 또, 다른 한 장소를 골라서 벌통을 둔다. 아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.

두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다. 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.

1. 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
2. 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.

위의 그림과 같이 배치된 경우 두 마리의 벌 모두 4+1+4+9+9=27의 꿀을 따서, 전체 꿀의 양은 54가 된다.

위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은 9+4+4+9+9=35의 꿀을 따고 오른쪽 장소에서 출발한 벌은 4+9+9=22의 꿀을 따므로, 전체 꿀의 양은 57이 된다.

위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.

장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.

입력

첫 번째 줄에 장소의 수 N이 주어진다.

다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.

출력

첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.

제한

•  3≤N≤100 000
• 각 장소의 꿀의 양은 1 이상 10 000 이하의 정수이다.

서브태스크

번호	배점	제한
1	11	N≤20
2	13	N≤500
3	31	N≤5 000
4	45	추가적인 제한이 없음.

예제 입력 1

7
9 9 4 1 4 9 9

예제 출력 1

57

예제 입력 2

7
4 4 9 1 9 4 4

예제 출력 2

54

예제 입력 3

3
2 5 4

예제 출력 3

10

알고리즘 분류

• 누적 합

풀이

꿀의 누적 합을 구하고, 다음과 같은 경우의 수를 따진다.

1. 꿀통이 벌 사이에 있는 경우(벌 - 꿀통 - 벌)

 - 이 경우에는 벌들이 양 끝에서 시작하는 것이 좋다.

2. 벌 2마리 오른쪽에 꿀통이 있는 경우(벌 - 벌 - 꿀통)

 - 이 경우에는 벌이 왼쪽 끝, 꿀통이 오른쪽 끝에 위치하고 벌 한마리가 위치를 바꾸면서 딸 수 있는 꿀의 최댓값을 구한다.

3. 벌 2마리 왼쪽에 꿀통이 있는 경우(꿀통 - 벌 - 벌)

 - 이 경우에는 꿀통이 왼쪽 끝, 벌이 오른쪽 끝에 위치하고 벌 한마리가 위치를 바꾸면서 딸 수 있는 꿀의 최댓값을 구한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9

using namespace std;
int N;
int Honey[MAX];
int Sum[MAX];
int Answer = 0;

void Input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> Honey[i];
		Sum[i] = Sum[i - 1] + Honey[i];
	}
}

void Settings() {
	// 1. 벌 - 꿀통 - 벌
	for (int i = 2; i < N; i++) {
		int Cur = (Sum[i] - Sum[1]) + (Sum[N - 1] - Sum[i - 1]);
		Answer = max(Answer, Cur);
	}

	// 2. 벌 - 벌 - 꿀통
	for (int i = 2; i < N; i++) {
		int Cur = (Sum[N] - Sum[1] - Honey[i]) + (Sum[N] - Sum[i]);
		Answer = max(Answer, Cur);
	}

	// 3. 꿀통 - 벌 - 벌
	for (int i = 2; i < N; i++) {
		int Cur = (Sum[N - 1] - Honey[i]) + Sum[i - 1];
		Answer = max(Answer, Cur);
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}