[백준] 21758번 - 꿀 따기 (C++) 문제 및 풀이

문제) 백준 - 그리디 알고리즘 - 꿀 따기

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

21758번: 꿀 따기

 

벌과 꿀통의 위치에 따라 최대 꿀의 양을 구합니다. 각 벌과 꿀통은 양쪽 끝에 위치해야 꿀의 최대를 가질 수 있습니다. (벌 벌 꿀), (벌 꿀 벌), (꿀 벌 벌) 순서로 최대 꿀의 양을 계산하며 누적 합을 이용하여 빠르게 구할 수 있습니다.

 

C++ 소스코드)

	#include <bits/stdc++.h>
	#define endl "\n"
	#define ll long long
	#define INF 987654321
	#define MAX 100001
	#define int ll
	using namespace std;
	typedef pair<int, int> p;
	int N;
	int Honey[MAX];
	int parSum[MAX];
	signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for(int i = 1; i <= N; ++i){
	cin >> Honey[i];
	parSum[i] = Honey[i] + parSum[i - 1];
	}
	int ans = 0;
	// 벌 벌 꿀
	for(int i = 2; i < N; ++i)
	ans = max(ans, parSum[N] - Honey[1] + parSum[N] - parSum[i] - Honey[i]);
	// 벌 꿀 벌
	for(int i = 2; i < N; ++i)
	ans = max(ans, parSum[i] - Honey[1] + parSum[N] - parSum[i - 1] - Honey[N]);
	// 꿀 벌 벌
	for(int i = 2; i < N; ++i)
	ans = max(ans, parSum[N] - Honey[N] + parSum[i] - Honey[i] - Honey[i]);
	cout << ans << endl;
	return 0;
	}

view raw 21758.cpp hosted with ❤ by GitHub