백준 21758: 꿀 따기

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

 

이 문제는 너무 어렵게 생각했던 것 같다.

 

초기엔 꿀통 위치를 조정하며 가장 최적의 위치를 구하면 되지 않을까란 생각을 했지만, 꿀벌 위치를 어떻게 할지를 고민을 많이 했다. 그런데, 머릿속에서 여러 반례를 떠올리다보니 적어도 하나의 꿀벌은 끝에 있다는 공통점을 발견했다. 그럼 그리디적으로 생각해서 꿀통도 늘 끝에 두고, 남은 꿀벌의 위치를 조정하며 답을 구하면 어떨까란 생각을 하게되었다. 그렇게 나온 코드는 다음과 같다.

#include <iostream>
#include <algorithm>

using namespace std;

int N, A[100001], S1 = 0, ans = 0, S2 = 0;

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	if (A[0] > A[N - 1]) reverse(A, A + N);
	for (int i = 1; i < N; i++) S1 += A[i];
	S2 = S1;
	for (int i = 1; i < N; i++)
	{
		S2 -= A[i];
		ans = max(ans, S1 - A[i] + S2);
	}
	cout << ans << '\n';
}

다만 이 코드는 예제 3을 통과하지 못한다. 왜냐하면 꿀통이 중간에 있을 가능성이 있기 때문이다. 이걸 N=3일 경우에만 있는 코너 케이스일 것이라고 단순하게 생각했었는데 다른 반례를 둘러보니 그건 아니였기에, 꿀통이 중간에 있을 경우를 고려해야했다.

 

그럼 꿀통이 중간에 있을 때, 꿀벌 위치는 어디에 둬야할까? 바로 양쪽 끝이다. 최대한 많은 장소를 방문해야하므로, 최대한 꿀통과 멀어져야한다.

 

정리하자면,

1. 꿀벌 위치가 양끝, 벌통 위치가 중간에 있는 경우

2. 꿀벌, 벌통이 양끝, 다른 꿀벌 하나의 위치가 중간.

 

이 두가지 가능성을 살피면 된다. 그렇게 나온 코드는 다음과 같다.

#include <iostream>
#include <algorithm>

using namespace std;

int N, A[100001], S1 = 0, ans = 0, S2 = 0;

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	if (A[0] > A[N - 1]) reverse(A, A + N);
	for (int i = 1; i < N; i++) S1 += A[i];
	S2 = S1;
	for (int i = 1; i < N; i++)
	{
		S2 -= A[i];
		ans = max(ans, S1 - A[i] + S2);
	}
	S1 -= A[N - 1];
	for (int i = 1; i < N - 1; i++)
		ans = max(ans, S1 + A[i]);
	cout << ans << '\n';
}

안타깝게도 이 코드도 틀렸다. 내가 너무 그리디적으로 생각해서, 끝의 벌 위치를 작은 양의 꿀을 딸 수 있는 위치로 정해버렸기 때문이다. 즉, 벌의 위치가 왼쪽 혹은 오른쪽인 두 경우로 나눠서 생각을 해야한다. 다시 정리하면

1. 벌이 양쪽, 꿀통 중간

2. 벌이 오른쪽, 꿀통 왼쪽, 벌 중간

3. 벌이 왼쪽, 꿀통 오른쪽, 벌 중간.

이 3가지 가능성을 전부 살펴봐야한다. 그렇게 나온 코드는 다음과 같다.

#include <iostream>
#include <algorithm>

using namespace std;

int N, A[100001], S1 = 0, ans = 0, S2 = 0;

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 1; i < N; i++) S1 += A[i];
	S2 = S1;
	for (int i = 1; i < N; i++)
	{
		S2 -= A[i];
		ans = max(ans, S1 - A[i] + S2);
	}
	S1 -= A[N - 1]; S1 += A[0];
	S2 = S1;
	for (int i = N - 2; i >= 0; i--)
	{
		S2 -= A[i];
		ans = max(ans, S1 - A[i] + S2);
	}
	S1 -= A[0];
	for (int i = 1; i < N - 1; i++)
		ans = max(ans, S1 + A[i]);
	cout << ans << '\n';
}

DP는 플레 중위권은 잘 푸는데, 어째서 그리디는 골드를 넘어가면 이렇게 고전하게 되는 것일까. 그리디 문제는 좀 더 연구를 해봐야겠다.