[백준] 골드 5, 꿀 따기

문제

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

21758번: 꿀 따기

알고리즘 분류

그리디

누적 합

 

 

문제가 벌꿀과 벌의 배치 조건이 3가지로 분류가 가능하다

 

1. 벌 벌 꿀통

2. 꿀통 벌 벌

3. 벌 꿀통 벌

살펴보면 3가지 조건 모두 양쪽 끝은 고정되고 벌 또는 벌통이 양끝을 제외한곳에서 변경이 이루어짐을 알 수 있었다.

 

내경우엔 단순히 반복문과 벡터요소 합으로 계산하여 구현을 시도했다.

아래와같은 코드로 시도했으나 100점이아닌 55점에서 그치고 말았고 이런저런 시도를 해봤지만 여기서 더 개선은 되지않았다.

for (int i = 1; i < N - 1;++i)
{
	//벌 벌 꿀통
	int value1 = accumulate(vec.begin() + 1, vec.end(), 0) - vec[i] + accumulate(vec.begin() + i + 1, vec.end(), 0);
	//꿀통 벌 벌
	int value2 = accumulate(vec.begin(), vec.end() - 1, 0) - vec[N - 1 - i] + accumulate(vec.begin(), vec.end() - 1 - i, 0);
	//벌 꿀통 벌
	int value3 = accumulate(vec.begin() + 1, vec.begin() + 1 + i, 0) + accumulate(vec.begin() + i, vec.end() - 1, 0);

	result = max(result,max(max(value1, value2),value3));
}

 

정답은 다른분의 코드를 참고하여 이해하게 되었다.

 

100점짜리 코드는 아래와 같다.

int main()
{
	int N;
	cin >> N;

	vector<int> honey(N + 1, 0);
	vector<int> sum(N + 1, 0);

	for (int i = 1; i <= N;++i)
	{
		cin >> honey[i];
		sum[i] = sum[i - 1] + honey[i];
	}
	int result = 0;

	for (int i = 2; i < N; ++i)
	{
		//벌 벌 꿀통
		int value1 = (sum[N] - sum[1] - honey[i]) + (sum[N] - sum[i]);
		//꿀통 벌 벌
		int value2 = (sum[N - 1] - honey[i]) + sum[i - 1];
		//벌 꿀통 벌
		int value3 = (sum[i] - honey[1]) + (sum[N - 1] - sum[i - 1]);

		result = max(result, max(max(value1, value2), value3));
	}

	cout << result << "\n";
}

알고리즘이 누적합으로 분류되었던이유가 이것이였다.

 

빨강 : sum[1], 초록 : sum[2], 파랑 sum[3]

sum에 배열 첫인덱스부터 의 누적합을 저장한뒤 이를 활용하는 방법으로 내가 vector의 accumulate를 사용했을때보다 코드도 훨씬 간결하게 정리가되었다. 덕분에 누적합관련 문제를 풀때 어떤방법을 사용해야될지 참고 할 수 있었다.