[백준] C++ 21758(꿀 따기)

 

#include <iostream>

using namespace std;

int arr[100001];

int main(void)
{
	int N=0;
	cin>>N;
	
	for(int i=0; i<N; i++)
	{
		cin>>arr[i];
	}
	
	for(int i=1; i<N; i++)
	{
		arr[i]=arr[i]+arr[i-1];
	}
	
	
	//right
	int result=(arr[N-1]-arr[0]) + (arr[N-1]-arr[1]) - (arr[1]-arr[0]);
	int i=2;
	while(true)
	{
		if(i>N-2)
		{
			break;
		}
		int temp=(arr[N-1]-arr[0]) + (arr[N-1]-arr[i]) - (arr[i]-arr[i-1]);
		if(result<temp)
		{
			result=temp;
		}
		
		i++;
	}
	
	//left
	int result2=(arr[N-2]) + (arr[N-3]) - (arr[N-2]-arr[N-3]);
	int j=4;
	while(true)
	{
		if(j>=N)
		{
			break;
		}
		int temp=(arr[N-2]) + (arr[N-j]) - (arr[N-j+1]-arr[N-j]);
		if(result2<temp)
		{
			result2=temp;
		}
		
		j++;
	}
	
	//middle
	
	int result3=(arr[1]-arr[0]) + (arr[N-2]-arr[0]);
	int l=2;
	while(true)
	{
		if(j>=N)
		{
			break;
		}
		int temp=(arr[l]-arr[0]) + (arr[N-2]-arr[l-1]);
		if(result3<temp)
		{
			result3=temp;
		}
		
		l++;
	}
	
	int max=0;
	
	if(max<result)
	{
		max=result;
	}
	if(max<result2)
	{
		max=result2;
	}
	if(max<result3)
	{
		max=result3;
	}
	cout<<max;

	
	return 0;
}

 

꿀벌 2마리가 꿀통으로 똑바로 날아가면서 얻은 꿀의 최댓값을 구하는 문제이다.

꿀벌은 서로 다른 위치에 존재하고 꿀통도 꿀벌과 서로 다른 위치에 존재한다.

꿀벌은 자기가 시작하는 위치의 꿀을 얻지 못한다.(최댓값을 구하기 위해 고려해야 할 주요 조건)

 

이 문제를 어떻게 접근해야 하는가??

for(꿀통) for(꿀벌 1) for(꿀벌 2) 3중 for문을 사용한다면?

이 문제를 for문을 3번 사용해서 풀게 되면 분명 시간초과가 발생할 것이다. 입력값으로 100,000까지 올 수 있기 때문이다.

 

그러면 어떤 방법으로 접근해야 하는가??

문제의 정확하게 이해해야 한다.

꿀통을 기준을 생각해 보자. 꿀통이 만약 맨 오른쪽에 위치한다면 꿀벌들은 맨 왼쪽에서 시작해야 할 것이다. 만약 꿀벌이 맨 왼쪽이 아니고 한 칸이라도 떨어진 곳에서 시작한다면 최댓값을 구하지 못한다.

잘못된 접근 방법

 

위 그림처럼 한 칸 뛰어진 위치에서 시작하는 것은 잘못된 접근 방법이다.

꿀벌 1은 맨 왼쪽에 고정되어야 한다. 꿀벌 2를 움직여서 최댓값을 찾아내면 된다.

 

꿀통이 맨 왼쪽에 있다면??

꿀벌 1을 맨 오른쪽에 고정시키고 꿀벌 2를 움직여서 위와 같은 작업을 수행해 주면 된다.

 

만약 꿀통이 맨 왼쪽도 아니고 맨 오른쪽도 아니라면??

맨 왼쪽에 꿀벌 1을 고정시켜 놓고 맨 오른쪽에 꿀벌 2를 고정시킨 후 꿀통을 그 사이에서 움직이면 된다.

 

왜 꿀벌을 맨 왼쪽과 맨 오른쪽에 고정시키는가?? 그렇게 해야 손해 보는 꿀 없이 최댓값을 구할 수 있기 때문이다.

위에서 찾은 result값 3개 중 가장 높은 값을 출력해 주면 된다.